실력키우기 참외밭(C++)

2259 : 참외밭

제한시간: 1000 ms    메모리제한: 32 MB
해결횟수: 604 회    시도횟수: 1889 회   

시골에 있는 태양이의 삼촌 댁에는 커다란 참외밭이 있다. 문득 태양이는 이 밭에서 자라는 참외가 도대체 몇 개나 되는지 궁금해졌다. 어떻게 알아낼 수 있는지 골똘히 생각하다가 드디어 좋은 아이디어가 떠올랐다. 유레카! 1㎡의 넓이에 자라는 참외 개수를 헤아린 다음, 참외밭의 넓이를 구하면 비례식을 이용하여 참외의 총개수를 구할 수 있다.

1㎡의 넓이에 자라는 참외의 개수는 헤아렸고, 이제 참외밭의 넓이만 구하면 된다. 참외밭은 ㄱ-자 모양이거나 ㄱ-자를 90도, 180도, 270도 회전한 모양(┏, ┗, ┛ 모양)의 육각형이다. 다행히도 밭의 경계(육각형의 변)는 모두 동서 방향이거나 남북 방향이었다. 밭의 한 모퉁이에서 출발하여 밭의 둘레를 돌면서 밭경계 길이를 모두 측정하였다.

 

예를 들어 참외밭이 위 그림과 같은 모양이라고 하자. 그림에서 오른쪽은 동쪽, 왼쪽은 서쪽, 아래쪽은 남쪽, 위쪽은 북쪽이다. 이 그림의 왼쪽위 꼭지점에서 출발하여, 반시계방향으로 남쪽으로 30m, 동쪽으로 60m, 남쪽으로 20m, 동쪽으로 100m, 북쪽으로 50m, 서쪽으로 160m 이동하면 다시 출발점으로 되돌아가게 된다.

위 그림의 참외밭 면적은 6800㎡이다. 만약 1㎡의 넓이에 자라는 참외의 개수가 7이라면, 이 밭에서 자라는 참외의 개수는 47600으로 계산된다.

1㎡의 넓이에 자라는 참외의 개수와, 참외밭을 이루는 육각형의 임의의 한 꼭지점에서 출발하여 반시계방향으로 둘레를 돌면서 지나는 변의 방향과 길이가 순서대로 주어진다. 이 참외밭에서 자라는 참외의 수를 구하는 프로그램을 작성하시오.

 

첫 번째 줄에 1㎡의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K(1≤K≤20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭지점에서 출발하여 반시계방향으로 둘레를 돌면서 지나는 변의 방향과 길이 (1 이상 500 이하의 정수) 가 둘째 줄부터 일곱 번째 줄까지 한 줄에 하나씩 순서대로 주어진다. 변의 방향에서 동쪽은 1, 서쪽은 2, 남쪽은 3, 북쪽은 4로 나타낸다.

첫째 줄에 입력으로 주어진 밭에서 자라는 참외의 수를 출력한다.

[Copy] 7 4 50 2 160 3 30 1 60 3 20 1 100

[Copy] 47600

출처 : KOI 본선 2010 초3/중2

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

/**************************************************************     Problem: 2259     User: a132034     Language: C++     Result: Success     Time:1 ms     Memory:1740 kb ****************************************************************/     #include    <iostream> using namespace std;   int main() {     int K;     int dir[6];     int len[6];     int size[7];     int farm = 0;     int widthMax = 0;     int heightMax = 0;     cin >> K;             for (int i = 0; i < 6; ++i)     {         cin >> dir[i] >> len[i];         if (dir[i] == 1 || dir[i] == 2)         {             if (len[i] > widthMax)                 widthMax = len[i];         }         else         {             if (len[i] > heightMax)                 heightMax = len[i];         }     }     //end input area           for (int i = 0; i < 5; ++i)     {         size[i] = len[i] * len[i + 1];         farm += size[i];     }     size[6] = len[0] * len[5];     farm += size[6];     farm -= widthMax*heightMax * 2;     cout << farm*K << endl;     return 0; }

사실 어려울 줄 알고... 이제야 풀어보기는 했는데 생각보다 어려운 문제는 아니었다. 

추가로 이 방법 외에도 더 뭔가 알고리즘적(?)이고 오묘하고 기묘한..? 뭔가 번뜩이는 방법이 있을 것 같으나. 

그림을 그려가며 생각해본 결과 이 방법이 가장 확실하겠다 싶은 마음에 이렇게 풀게 되었다. 

우선 주어진 조건

1. 6각형이다. 

2. 밭은 ㄱ ㄴ 등의 모양으로 사각형들의 합으로 만들 수 있는 6각형이다. 

조건을 생각하며 그림을 그려보니... 입력된 높이(남, 북 방향) 중 가장 큰 높이값과 너비(동, 서 방향) 중 가장 큰 너비값의 곱에서 작은 사각형이 하나 빠진 그림이 된다는걸 생각해내고는.. 저 작은 사각형을 어떻게 구할까... 고민해보았다. 

우선

조건에 만족하는 6각형은 딱 4가지가 있다. 

1~4번 사각형 중 한 군데가 빈 모양이 나오게 된다. 

1	2
3	4

그리고 입력받는 순서는 무조건 동서방향이 나온 후에는 남북방향, 남북방향이 나온 후에는 동서방향(가로 -> 세로 또는 세로 -> 가로)이므로 

입력받은 순서대로 너비를 구하면.. 너비는 무조건 1,2,3,4의 조합으로 나오게 된다. 

이를 전부 합쳐보면 모든 구한 너비의 합은 

전체너비 + 전체너비 + 구하고자하는 6각형의 너비 가 되고

여기서 전체너비*2를 제하여주면 원하는 너비를 구할 수 있다. 

ex) 예제입력의 경우 

7

4 50

2 160

3 30

1 60

3 20

1 100

이므로 

50 * 160 -> 1+2+3+4 전체 너비 

160 * 30 -> 1+2

30 * 60   -> 1

60 * 20   -> 3(빼고자 하는 너비)

20 * 100 -> 4

100 * 50 -> 2 + 4 (100을 입력받았고 다음 입력이 없지만 6각형이 완성되는 부분이므로 처음 입력받은 50을 이용)

전부 더하면 

1 + 2 + 3 + 4

+ 1 + 2 + 1 + 3 + 4 + 2 + 4 

=> 1 + 1 + 1 + 2 + 2 + 2 + 3 + 3 + 4 + 4 + 4 => 빼고자 하는 너비만 2번 포함되며 나머지는 3번씩 포함되는 것을 확인할 수 있다.