백준 2477번 - 참외밭

www.acmicpc.net/problem/2477

2477번: 참외밭

실버 5의 구현 문제여서 쉬울 것이라고 생각하고 접근했다가 엄청 애먹었다...

 

문제를 보면 다들 큰 사각형에서 작은 사각형 빼면 되겠다!라고 생각할 것이다.

근데 어떻게 작은 사각형을 구하지...?

이 고민만 30분 넘게 했다.

 

다양한 방법이 생각났지만 아무리 봐도 실버5에 쓸만한 구현들이 아니었다.

분명 더 쉬운 풀이법이 있을 것 같은데...

 

결국 내가 마지막으로 생각해 낸 방법은 4가지 도형으로 나누어서 각 도형별로 어느 방향에서 어느 방향으로 가면 작은 사각형인지 알아내는 방법이었는데 구현하기가 너무 귀찮았다.. (굳이 설명하지 않아도 될 것 같음)

 

그래서 구글의 도움을 빌려 알아낸 방법은 다음과 같다.

두 번째로 나오는 잘리지 않은 변(큰 사각형의 가로 또는 세로)의 인덱스 + 2번째와 +3번째에는 반드시 작은 사각형의 가로와 세로의 길이가 나온다! 이다.

 

이렇게 말하면 이해가 잘 안 되니 간단하게 설명해 보자면

이 문제의 조건에 따라 무조건!!! 반시계 방향으로 변들의 정보가 주어지기 때문에

반드시!!! 첫 번째 잘리지 않은 변과 두 번째 잘리지 않은 변은 index가 1 차이, 즉 붙어있을 것이다.

(어떤 모양이든 위의 가정은 항상 성립한다.)

 

따라서 두 번째 잘리지 않은 변을 찾는다면 그에 따라 index+2와 index+3인 변의 정보를 가져다 쓰면 된다.

 

이 와중에도 여러 가지 함정이 있다.

그냥 index+2, +3 하면 당연히 런타임 에러 날 수 있으므로 조심해야 하고

 

만약 위의 그림에서 두 번째 잘리지 않은 변의 index가 0이라면? 

이것 때문에 한번 틀렸었는데..

어쨌든 두 개의 잘리지 않은 변 중 index가 큰 경우를 찾아버리면 저 경우 첫 번째 잘리지 않은 변의 index가 5가 되고, 그다음 변의 index가 0이 되기 때문에 작은 사각형을 계산할 때 잘못된 변으로 계산하게 된다..

 

간단한 예외처리를 통해 해결할 수 있다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    int k, n, a;
    vector<pair<int, int>>v;
    cin >> k;
    int EW = 0;
    int NS = 0;      
    for (int i = 0; i < 6; i++) {
        cin >> n >> a;
        v.push_back(make_pair(n, a));
        if (n >= 3) NS += a;
        else EW += a;
    }
    NS /= 2;    // 큰 정사각형의 위, 아래 변의 길이
    EW /= 2;    // 큰 정사각형의 왼쪽, 오른쪽 변의 길이
    int index = -1;
    bool check = false;
    for (int i = 0; i < 6; i++) {
        // 현재 인덱스가 잘리지 않은 변인지 판단
        if (v[i].second == NS || v[i].second == EW) {
            int k = i + 1;
            if (k > 5) k = 0; // 현재 index가 5, 즉 배열의 마지막이라면
            // 다음 index는 0이 되어야 한다.
            // 다음 인덱스도 잘리지 않은 변이라면 "찾았다!!"
            if (v[k].second == NS || v[k].second == EW) {
                index = k;
                break;
            }
        }
    }
    int x = index + 2;
    int y = index + 3;
    if (x > 5)x -= 6;
    if (y > 5)y -= 6;
    // (큰 정사각형의 넓이 - 작은 정사각형의 넓이) * k
    cout << ((NS * EW) - (v[x].second * v[y].second)) * k << "\n";
}