백준 2477번 참외밭 :: 마이구미

이 글은 백준 알고리즘 문제 2744번 "참외밭" 풀이한다.

정올 초등부, 중등부 문제에 출제된 문제이다.

풀이는 수학적 사고를 요구하는 문제가 된다.

문제 링크 - https://www.acmicpc.net/problem/2477

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

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

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

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

4개의 방향과 모양이 존재하는 모습에 자칫 어렵게 볼 수도 있다.

하지만 순수하게 생각해보면, 다음과 같은 접근을 할 것이다.

1. 160 * 50 을 통해 전체 사각형의 넓이를 구한다.
2. 60 * 20 을 통해 비어있는 사각형의 넓이를 뺀다.

본인은 방향은 신경쓰지 않았다.

왜냐하면, 비어있는 사각형의 너비와 높이를 어떻게 구할 것인지에 집중했다.

그 결과 규칙을 찾을 수 있었다.

한 변을 기준으로 이 변이 너비라고 가정하자.

그림을 보면, 기준 변의 반시계 방향의 변과 시계 방향의 변은 높이라는 것을 알 수 있다.

(기준 변이 array[i] 이고, 반시계 방향의 변이 array[i - 1], 시계 방향의 변이 array[i + 1] 이라고 볼 수 있다.)

위 그림에서 60 길이의 변을 확인해보자.

width = 160
height = 50

array[i] = 60
array[i - 1] = 30
array[i + 1] = 20

50(height) == array[i - 1] + array[i + 1]

20 길이의 변을 확인해보자.

array[i] = 20
array[i - 1] = 60
array[i + 1] = 100

160(width) == array[i - 1] + array[i + 1]

array[i - 1] + array[i + 1] 이 전체 사각형의 너비 또는 높이일 경우가 빈 사각형을 의미하는 것을 볼 수 있다.

모든 변의 길이를 돌면서, 너비와 높이에 대해 각각 찾아주면 된다.

주의할 점은 인덱스가 -1 이 될 수도 있고, 배열의 크기를 넘을 수도 있다.

각각의 경우에 대해 분기처리를 할 수도 있지만, 규칙을 찾아 나머지 연산을 활용할 수도 있다.

자세한 건 코드를 통해 확인하길 바란다.

private void solve() {
    int k = sc.nextInt();
    int[] array = new int[6];
    int w = 0;
    int h = 0;
    int ww = 0;
    int hh = 0;
    for (int i = 0; i < 6; i++) {
        sc.nextInt();
        array[i] = sc.nextInt();
    }
 
    // Get, max width and height
    for (int i = 0; i < 6; i++) {
        if (i % 2 == 0) {
            if (w < array[i]) {
                w = array[i];
            }
        } else {
            if (h < array[i]) {
                h = array[i];
            }
        }
    }
 
    // 한 변을 기준으로 앞 뒤 변의 길이의 합이 길이와 같다면 파인 지점
    for (int i = 0; i < 6; i++) {
        if (i % 2 == 0) {
            if (h == array[(i + 5) % 6] + array[(i + 1) % 6]) {
                ww = array[i];
            }
        } else {
            if (w == array[(i + 5) % 6] + array[(i + 1) % 6]) {
                hh = array[i];
            }
        }
    }
    System.out.println((w * h - ww * hh) * k);
}