(C)참외밭 백준 2477번

백준 2477번이자 한국 정보 올림피아드 2010년도 기출 문제 풀이입니다.

#include <stdio.h>

int main (void){
    int melons_per_square_meter,esnw[7][2]={0};
    int length[7],multiple=1,to_sub=1;
    
    /**1 제곱미터당 참외 개수 입력 받기**/
    
    scanf("%d",&melons_per_square_meter);
    
    /**입력받기**/
    
    for (int i=0;i<6;i++)
    {
        scanf("%d %d",&esnw[i][0],&length[i]);
    }
    
    /**큰 직사각형의 성분이면 0, 아니면 1 저장해주기**/
    for(int i=0;i<6;i++)
    {
        for(int j=i+1;j<6;j++)
        {
            if(esnw[i][0]==esnw[j][0])
            {
                esnw[i][1]=1; esnw[j][1]=1;
            }
        }
    }
    
    /**작은 직사각형의 조건: 전후의 변이 큰 직사각형의 성분이 아니여야함. ->배열 값 세 개 연달아 1**/
    for(int i=0;i<6;i++)
    {
        if(esnw[i][1]==1&&esnw[(i+5)%6][1]==1&&esnw[(i+1)%6][1]==1)
            to_sub*=length[i];
        if(esnw[i][1]==0)
            multiple*=length[i];
    }
    
    
    int ans= (multiple-to_sub)*melons_per_square_meter;
    
    printf("%d",ans);
    
}

이 문제의 핵심 아이디어는 너무도 간단하다.
큰 직사각형- 작은 직사각형을 하는 것이다.
 

1. 큰 직사각형 찾는 방법

큰 직사각형의 양변은 변의 방향이 한 번만 나온다.두 번 나오면 esnw[][i]배열을 1로 바꿔준다.
esnw[][i]=0인 값들을 곱해주면 큰 직사각형이 나온다.

2. 작은  직사각형 찾기

작은 직사각형의 양변은 자기 자신 전의 변과 다음 변 모두가 큰 직사각형의 변이 아니어야 한다.

if(esnw[i][1]==1&&esnw[(i+5)%6][1]==1&&esnw[(i+1)%6][1]==1)
      to_sub*=length[i];

 
 
다음이 구현한 코드이다.
나누기를 해주어야 하는 것이 특징이다.(원형 큐와 동일한 아이디어)
 
이를 구현하였으면 큰 직사각형에서 작은 직사각형을 제외해주면 된다.