BOJ 15685 - 드래곤 커브

www.acmicpc.net/problem/15685

15685번: 드래곤 커브

 

방향 회전에 대한 부분을 도통 어떻게 처리해야 될지 감을 못잡다가

다른 블로거 분들의 해설을 보고 이해하게 되었다.

 

k번째 세대의 드래곤 커브는 k - 1 번째 세대의 드래곤 커브의 방향 값을 

역순으로 +1 하면서 나열하여 이어 붙이는 식으로 찾아낸다.

 

문제에서 방향에 대한 값을 다음과 같이 정의했다

0 : 오른쪽 방향, 1 : 위쪽 방향, 2 : 왼쪽 방향, 3 : 아랫쪽 방향

 

문제의 설명 부분에 예시로 든것을 보면

(처음 방향이 오른쪽 (d = 0) 일때)

 

0세대 :  0 (방향값)

1세대 :  0 1

2세대 :  0 1 2 1

3세대 :  0 1 2 1 2 3 2 1

4세대 :  0 1 2 1 2 3 2 1 2 3 0 3 2 3 2 1

..... 이런식으로 진행된다.

 

이전 세대가 가지고 있던 방향 값을 역순으로 나열하되 +1 을 하여 역순으로 나열한다

다만 4를 초과하면 안되므로 4의 나머지 값으로 처리한다.

 

- c++

 

#include <iostream>
#include <vector>
 
#define MAX 101
 
using namespace std;
 
int n, answer;
int x, y, d, g;
int adj[MAX][MAX];
int dy[4] = {0, -1, 0, 1};
int dx[4] = {1, 0, -1, 0};
vector<int> pos;
 
int count_square() {
    int cnt = 0;
    for (int i = 0; i < MAX; ++i) 
        for (int j = 0; j < MAX; ++j) 
            if (adj[i][j] == 1 && adj[i][j + 1] == 1 && adj[i + 1][j] == 1 && adj[i + 1][j + 1] == 1) cnt++; 
    return cnt;
}
 
void make_dragon_curve() {
    int size = pos.size();
    for (int i = size - 1; i >= 0; --i) {
        int nd = (pos[i] + 1) % 4;
        y = y + dy[nd];
        x = x + dx[nd];
        adj[y][x] = 1;
        pos.push_back(nd);
    }
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n;
    for (int i = 0; i < n; ++i) {
        pos.clear();
 
        cin >> x >> y >> d >> g;
        
        adj[y][x] = 1;
        y = y + dy[d];
        x = x + dx[d];
        adj[y][x] = 1;
        
        pos.push_back(d);
        for (int j = 0; j < g; ++j) make_dragon_curve();
    }
    
    answer = count_square();
    cout << answer;
    
    return 0;
}

 

 

 

 

 

점점 골드 이상의 문제들을 풀다보니

순전히 내힘으로 푸는 문제의 갯수가 확 줄어들고 있다..