15685번-드래곤커브

문제

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

15685번: 드래곤 커브

---

접근방법

1) 접근 사고

단순 구현 문제인데 "드래곤 커브의 회전을 어떻게 구할 것인가?"라는 명제가 핵심인 문제였습니다. 처음에는 재귀함수로 구현을 할 생각을 했었는데 0 ~ n 세대 순으로 증가하기 때문에 각 방향에서 방향의 크기만큼 한 번더 회전을 해주면 총 드래곤 커브의 회전량이 나오기 때문에 재귀함수로 구현하지는 않았습니다. 

 

2) 시간 복잡도

O(n^2)

 

3) 배운 점

구현 문제는 규칙을 찾아야 한다. 계속 새로운 것을 시도해보자

 

4) PS

15684번과 유사한 선분문제인데 이런 문제에 너무 어려움을 느낀다. 다시 한 번 풀어봐야 할 꺼 같다.

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
 
const int MAX = 101;
int n;
int board[MAX][MAX];
int moveY[] = {0, -1, 0, 1};
int moveX[] = {1, 0, -1, 0};
 
int main(void)
{
    fastio;
    cin >> n;
    for(int i = 0; i< n; i++){
        int x ,y , d, g;
        cin >> x >> y >> d >> g;
 
        vector<int> dir;
        dir.push_back(d);
        //드래곤 커브의 모든 위치 변환값을 담아준다.
        for(int i = 1; i <= g; i++){
            int len = (int)dir.size() - 1;
            //세대만큼 회전해야 할 방향을 미리 정해준다.
            for(int j  = len; j >= 0; j--)
                dir.push_back((dir[j] + 1) % 4);
        }
        //초기 드래곤 커브 좌표 체크
        board[y][x] = true;
        //드래곤 커브 위치를
        for(int i = 0; i < dir.size(); i++){
            y = y + moveY[dir[i]];
            x = x + moveX[dir[i]];
            board[y][x] = true;
        }
    }
 
    //1*1 정삭각형을 확인해준다.
    int ret = 0;
    for(int y = 0; y < 100; y++){
        for(int x = 0; x < 100; x++){
            if(board[y][x] && board[y][x + 1] && board[y + 1][x] && board[y + 1][x + 1])
                ret++;
        }
    }
    cout << ret << "\n";
}