[백준][삼성 SW 역량 테스트][Gold 4][C++] 15685 드래곤 커브

문제

백준 삼성 SW 역량 테스트 기출 문제 - 15685 드래곤 커브 (Gold 4)

15685번: 드래곤 커브

 

---

문제 풀이

접근 방식

정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 문제이다.

드래곤 커브는 이전 세대의 커브를 시계 방향으로 90도 회전시켜 끝 점에 붙인 형태로 만들어진다.

 

우선, 이렇게 만들어지는 드래곤 커브에 규칙성이 있는지를 확인해보았다.

방향이 0으로 시작하는 커브의 경우 0 - 01 - 0121 - 01212321 - ... 의 형태로 만들어지는 것을 확인하였고,

이를 통해 다음 세대의 커브는 이전 세대의 값에 그 값을 뒤집어서 1씩 더해준 값을 합친 결과라는 것을 알게 되었다.

(방향이 0인 커브의 3세대 생성 과정 : 0121 + 0121을 뒤집은 값인 1210에 1씩 더한 값(2321) = 01212321)

 

그래서 주어진 드래곤 커브를 위의 규칙성을 활용하여 map에 그려주었고,

그 후 map에서 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 세어주어 답을 구하였다.

 

---

풀이 코드 - C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 입력 받기
    int N;
    cin >> N;
    vector<vector<int>> dragon(N, vector<int>(4));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 4; j++) {
            cin >> dragon[i][j];
        }
    }

    // 드래곤 커브 그리기
    int map[101][101] = {0};
    int dir[4][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
    for (int i = 0; i < N; i++) {
        int y = dragon[i][0];
        int x = dragon[i][1];
        int d = dragon[i][2];
        int g = dragon[i][3];
        map[x][y] = 1;
        vector<int> DP;
        DP.push_back(d);
        for (int j = 0; j < g; j++) {
            vector<int> temp = DP;
            reverse(temp.begin(), temp.end());
            int tlen = temp.size();
            for (int t = 0; t < tlen; t++) {
                temp[t] = (temp[t] + 1) % 4;
                DP.push_back(temp[t]);
            }
        }

        for (int k = 0; k < DP.size(); k++) {
            int dx = dir[DP[k]][0];
            int dy = dir[DP[k]][1];
            x = x + dx;
            y = y + dy;
            map[x][y] = 1;
        }
    }

    // 정사각형 개수 찾기
    int answer = 0;
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            if (map[i][j] == 1) {
                if (map[i][j + 1] && map[i + 1][j] && map[i + 1][j + 1])
                    answer++;
            }
        }
    }

    cout << answer;
}

실행 결과

실행 결과 : 통과 (0ms)