정보올림피아드 문제 입니다

조회수 463회

정보올림피아드 참외밭 문제 ( http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1520&sca=2060 ) 인데요.

모르겠어서 답안지를 봤는데, 의외로 짧은 코드가 나와서 놀랐습니다.

#include <stdio.h>

int main() {
    int K;
    scanf("%d", &K);

    int paper[500][500] = { 0, };
    int six[6][2] = { 0, };

    int farm = 0;

    int max_width = 0;
    int max_height = 0;


    for (int i = 0; i < 6; i++) {
        scanf("%d %d" , &six[i][0] , &six[i][1]);

        if (six[i][0] == 1 || six[i][0] == 2) {


            if (six[i][1] > max_width) {
                max_width = six[i][1];
            }
        }
        else if (six[i][0] == 3 || six[i][0] == 4) {


            if (six[i][1] > max_height) {
                max_height = six[i][1];
            }
        }

    }

    for (int i = 0; i < 5; i++) {

        farm += (six[i][1] * six[i + 1][1]);
    }

    farm += (six[0][1] * six[5][1]);

    farm -= max_width * max_height * 2;


    printf("%d" , farm * K);





}

그런데 마지막 즈음에

    farm -= max_width * max_height * 2;

이 부분은 아무리 봐도 이해가 안되더군요. 사각형을 잘라서 farm 에 합치는 과정은 이해 되는데, 왜 저 부분을 빼는지...

구체적인 설명을 해주셨으면 좋겠습니다.

1 답변

  • 문제에서는 6각형을 이루는 6개의 경계를 순회하고 있습니다.

    솔루션에서는 임의의 한 선분에서부터 순회하면서 넓이값을 누적하여 농장의 넓이를 구하려고 하네요.

    문제에서 주어진 선분은 6개이고 연속적입니다.

    1. [가로1, 세로1, 가로2, 세로2, 가로3, 세로3]
    2. [세로1, 가로1, 세로2, 가로2, 세로3, 가로3]

    위의 두 경우 중, 하나의 순서로 되어 있습니다. 첫 번째 경우로 가정해보죠.

    이제부터 그림을 그려서 따라해 보세요. 색은 6개가 필요합니다.

    인접한 값끼리 곱한 부분을 색칠합니다. (for 문에 해당)

    마지막에는 0번째 값과 곱한 걸 사용합니다. (six[0][1] * six[5][1]에 해당)

    • [가로1, 세로1]
    • [세로1, 가로2]
    • [가로2, 세로2]
    • [세로2, 가로3]
    • [가로3, 세로3]
    • [세로3, 가로1]

    위 6개의 넓이에 해당하는 영역을 모두 다른 색으로 색칠해 보셨다면, 오목하게 들어간 부분(concave)을 제외하고 다른 영역은 모두 3번 덧칠해져 있을 겁니다.

    오목한 부분은 2번 덧칠해져 있을 거고요.

    그래서 max값을 가진 가로, 세로 넓이를 두 번 빼주는 겁니다. (max_width * max_height * 2)

    그러면 3번 덧칠 된 육각형 내부의 넓이만 남겠죠.

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)