컴퓨터기본/문제풀이

[백준] 2477번: 참외밭

차가운오미자 2021. 9. 26. 10:22

https://www.acmicpc.net/problem/2477

 

2477번: 참외밭

첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지

www.acmicpc.net

문제 이해

주어지는 입력 중에, 각 요소가 어느 위치의 길이인지를 파악하는 것이 관건이다. 

주어질 수 있는 경우는 ㄱ,┏, ┗, ┛ 네 개이다. 

 

ㄱ 모양의 경우에 한 번 씩 나오는 방향의 길이가 큰 사각형이 너비(North), 높이(West)이고,

두 번씩 나오는 방향(South, East)의 길이들 중에, 껴있는 것이 작은 사각혐의 너비, 높이이다. 

다시 말해서 East방향의 길이들 중에서도 South 두 개 사이에 끼어있는 East길이가 너비이고,

South 방향의 길이들 중에서도 East 두 개 사이에 끼어있는 South길이가 높이이다. 

 

4 50

2 160

3 30

1 60

3 20

1 100

 

이러한 규칙은 다른 모양의 밭에도 적용된다. 두 번째 그림의 ┏ 모양 밭에서도

3 50

1 100

4 20

1 60

4 30

2 160

한 번씩 나오는 방향인 South(3)과 West(2)의 길이(즉, 큰 사각형의 높이와 너비이고)두 번씩 나오는 방향들 중에, 끼어있는 애들 (60 과 20)이 작은 사각형의 너비와 높이이다. 

 

이런 특징을 이용하면 어느 모양의 밭이라도, 쉽게 큰 사각형과 작은 사각형의 넓이를 구해, 답을 찾을 수 있다. 단 이때, 방향은 항상 동일하되, 시작점이 다르기 때문에 modulo 연산을 이용해서 껴있는지를 파악해야 한다. 

 

작성 코드

#include <stdio.h>

int N;
int arr[6 + 2][2 + 2];  // 주어지는 방향, 길이쌍
int cnt[4]; // 방향 별 등장 횟수 저장

int main(void) {
    
    int s = 1; // 작은 사각형의 넓이
    int b = 1; // 큰 사각형의 넓이

    // 입력 받기
    scanf("%d", &N);
    for (int i = 0; i < 6; i++) {
        scanf("%d %d", &arr[i][0], &arr[i][1]);
        cnt[arr[i][0]]++;
    }

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

        if (cnt[arr[i][0]] == 1) {
            // 한 번씩 등장하는 방향이다
            b *= arr[i][1]; // 큰 사각형의 너비/높이이다
            continue;
        }

        int n = (i + 1) % 6;
        int nn = (i + 2) % 6;
        // 나(I)랑 다다음거(nn)랑 같으면 그 사이에 있는 것(n)이 작은 사각형의 너비/높이이다.
        if (arr[i][0] == arr[nn][0]) s *= arr[n][1];
    }

    printf("%d", (b - s) * N);

    return 0;
}