• 백준 2477번 참외밭 :: 마이구미
    알고리즘 풀이/수학 2017. 12. 28. 00:44
    반응형

    이 글은 백준 알고리즘 문제 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 이 될 수도 있고, 배열의 크기를 넘을 수도 있다.

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

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


    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
    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 % == 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 % == 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);
    }
    cs


    반응형

    댓글

Designed by Tistory.