백준 15685번 - 드래곤 커브

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

시작점을 기준으로 계속해서 선분을 덧붙여 나간다.

선분의 개수는 0세대는 1개, 1세대는 2개, 2세대는 4개.... n세대는 2^(n-1)인 것을 알 수 있다.

처음 문제를 보면 설명이 굉장히 길고 어떻게 접근해야할지 감이오지 않았다.

그러다가 방향에 따라서 선분을 이어나갈 때 규칙이 있다는 것을 발견했다.

0부터 3까지의 값이 방향값이라고 문제에 명시 되어 있다.

처음 문제에 나온 예시를 방향값으로 정리하면 다음과 같다.

(0,0을 기준으로)

0세대 : 0

1세대  :  0 / 1

2세대 : 0, 1 / 2, 1

3세대 : 0, 1, 2, 1 / 2, 3, 2, 1

위의 방향값을 보면

N세대의 경우 N-1세대의 마지막 값부터 초기값까지 각각 1을 더한 것을 덧붙인다는 것을 알 수 있다.

즉, 3세대일때는 기존 2세대의 0,1,2,1 방향값에서 반대 방향으로 1씩 더한 2,3,2,1을 덧붙이면 되는 것이다.

계산한 방향값을 기준으로 선분을 이어 붙이면서 x,y 좌표에 표시하고 

총 4가지 꼭지점이 표시된 부분이 하나의 정사각형일때

몇개의 정사각형인지 (0,0)에서 (100,100)좌표까지 구하면 된다.

#include <iostream>
#include <vector>
using namespace std;
 
int dy[4]={0,-1,0,1};
int dx[4]={1,0,-1,0};
 
int main(){
    
    int N;
    cin>>N;
    
    int x,y,d,g;
    int map[101][101]={0};
    int ans=0;
    
    for(int n=0;n<N;n++){
        scanf("%d %d %d %d",&x,&y,&d,&g);
        vector<int> dir;
        dir.push_back(d);
        
        //g세대까지 방향값 저장
        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);
            }
        }
        
        //g세대까지 구한 방향값 좌표 저장
        map[y][x]++;
        for(int i=0;i<dir.size();i++){
            y=y+dy[dir[i]];
            x=x+dx[dir[i]];
            
            map[y][x]++;
        }
        
    }
    
    //(i,j) (i,j+1) (i+1,j) (i+1,j+1) 사각형 좌표 확인
    for(int i=0;i<100;i++){
        for(int j=0;j<100;j++){
            if(map[i][j] && map[i][j+1] && map[i+1][j] && map[i+1][j+1])
                ans++;
        }
    }
    
    cout<<ans<<endl;
    return 0;
}