[C++] 백준 2477번 참외밭

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

풀이

육각형은 (a, b, a, b, c, d) 와 같은 방향 순서를 만족한다.
"a, b" 패턴이 2번 연속으로 반복되고, 반복되지 않는 "c", "d"가 하나씩 존재해야 한다.

그리고 참외밭의 넓이는 (큰 직사각형 - 작은 직사각형)으로 구할 수 있다.
큰 직사각형은 c d로 구할 수 있고, 작은 직사각형은 (a, b, a, b) 수열에서 2, 3번째 요소인 b a로 구할 수 있다.

이를 이용하여 입력받은 방향을 a, b, c, d로 구별하고 넓이를 구한다.

오답

벡터 twice에 두번 반복되는 a, b의 인덱스를 저장한다. (2개의 a와 b 중 먼저 나오는 것) 그리고 벡터 once에 c, d의 인덱스를 저장한다.

그러나 이 코드는 틀렸다.

(a, b, a, b, c, d)처럼 수열 (a, b, a, b)가 쭉 이어져 있을 수도 있지만,
(a, b, c, d, a, b) 또는 (b, a, b, c, d, a)처럼 수열의 맨앞과 뒤에 있을 수도 있다는 점을 간과했기 때문이다.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int k, dir, len;
    vector<pair<int, int>> hexagon;
    
    cin >> k;
    for(int i=0; i<6; i++) {
        cin >> dir >> len;
        hexagon.push_back({dir, len});
    }
    
    vector<int> twice;
    for(int i=0; i<6; i++) {
        int cnt = 0;
        if(hexagon[i].first == hexagon[i+2].first) twice.push_back(i);
        if(twice.size() == 2) break;
    }
    
    vector<int> once;
    for(int i=0; i<6; i++) {
        if(i == twice[0] || i == twice[1]) continue;
        once.push_back(i);
    }
    
    int area = hexagon[once[0]].second * hexagon[once[1]].second 
                - hexagon[twice[0]+2].second * hexagon[twice[1]].second;
    cout << k * area;
    
    return 0;
}

정답

첫번째로 등장하는 a를 찾아보자. a b a b 형태를 만족하려면

• i번째 숫자 == i+2번째 숫자
• i+1번째 숫자 == i+3번째 숫자
  일 것이다. 그런데 수열의 맨 앞과 뒤에 분리되어 존재할 수도 있으므로,
• i번째 숫자 == (i+2)%6 번째 숫자
• (i+1)%6 번째 숫자 == (i+3)%6 번째 숫자
  이면 i번째 숫자가 a이다.

a 하나만으로도 a, b, c, d의 위치를 모두 표현할 수 있기 때문에 b의 위치는 저장하지 않고, a의 위치만 twice에 저장해도 된다.

• twice: 첫번째 a
• (twice+1)%6: 첫번째 b (작은 사각형의 한 변)
• (twice+2)%6: 두번째 a (작은 사각형의 한 변)
• (twice+3)%6: 두번째 b
• (twice+4)%6: c
• (twice+5)%6: d

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int k, dir, len;
    vector<pair<int, int>> hexagon;
    
    cin >> k;
    for(int i=0; i<6; i++) {
        cin >> dir >> len;
        hexagon.push_back({dir, len});
    }
    
    int twice;
    for(int i=0; i<6; i++) {
        int a1 = hexagon[i].first;
        int a2 = hexagon[(i + 2) % 6].first;
        int b1 = hexagon[(i + 1) % 6].first;
        int b2 = hexagon[(i + 3) % 6].first;
        if(a1 == a2 && b1 == b2) {
            twice = i;
            break;
        }
    }
    
    int big_area = hexagon[(twice + 4) % 6].second * hexagon[(twice + 5) % 6].second;
    int small_area = hexagon[(twice + 1) % 6].second * hexagon[(twice + 2) % 6].second;
    cout << k * (big_area - small_area);
    
    return 0;
}