[BOJ] 백준 2641 다각형그리기 (KOI 1999 초등부)

문제 링크

www.acmicpc.net/problem/2641

2641번: 다각형그리기

 

풀이

주어진 표본 모양 수열의 어디서 시작하든, 그 길이만큼만 똑같이 돌려주면 같은 모양의 다각형을 만들 수 있습니다.

 

문제 예제의 1411433322을 예로 들어봅시다.

1411433322

4114333221

1143332214

1433322141

...

2141143332

이렇게 10개의 표본 모양수열이 같은 다각형을 그리게 됩니다.

 

여기에 역방향으로 돌리는 경우까지 생각해줍시다

예제의 표본 모양수열을 역방향으로 만들면 위 - 아래, 오른쪽 - 왼쪽이 바뀌고, 수열의 순서 또한 뒤집어집니다.

1411433322 <-> 4411123323

이 형태의 표본 모양수열 또한 같은 다각형을 그립니다.

 

이렇게 같은 모양을 그리는 표본 모양 수열을 모두 저장하고 쿼리로 들어온 수열이 그 안에 포함되는지 판단하면 됩니다.

 

정답 코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
using namespace std;

int n, q;

vector<string> p;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    string s;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s += to_string(x);
    }
    s += s;
    
    for (int i = 0; i < n; i++) {
        string x;
        for (int j = 0; j < n; j++) {
            x += s[i + j];
        }
        p.push_back(x);
    }
    
    for (int i = 0; i < n * 2; i++) {
        int x = s[i] - '0' - 1;
        s[i] = (x + 2) % 4 + '0' + 1;
    }
    reverse(all(s));
    
    for (int i = 0; i < n; i++) {
        string x;
        for (int j = 0; j < n; j++) {
            x += s[i + j];
        }
        p.push_back(x);
    }

    cin >> q;
    vector<string> ans;
    while (q--) {
        string ss;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            ss += to_string(x);
        }
        if (find(all(p), ss) != p.end()) ans.push_back(ss);
    }
    cout << ans.size() << '\n';
    for (string i: ans) {
        for (char c: i) {
            cout << c << ' ';
        }
        cout << '\n';
    }
}