백준 15685. 드래곤 커브

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

15685번: 드래곤 커브

 

처음에 삽질해서 좀 시간이 걸린 문제다.

처음에 시도한 방법은 실제로 선분을 90도 돌려서 다음 세대의 드래곤 커브를 구하는 방법이었다.

구현하다가 이 방법은 90도 돌릴때마다 100*100 만큼의 연산이 필요했고, 끝점을 기준으로 90도를 돌리는게 생각보다 쉽지 않아 다시 생각해봤다.

 

결국 새로 생기는 다음 세대의 방향정보의 패턴을 알아냈다.

0세대: 0 

1세대: 0 1 

2세대: 0 1 2 1 

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

 

패턴을 보면 현재 세대를 뒤집은 후 1씩 더한 후 현재 세대의 뒤에 붙이면 다음 세대의 방향이다.

그리고 방향은 {0, 1, 2, 3}  총 4방향 이기 때문에 1을 더했는데 4가 나온다면 0이 되도록 % 연산을 이용하면 된다.

 

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

 

이렇게 방향정보를 구했으면 이제 이 방향대로 선분을 표시하는데 나는 bool형 2차원 배열에 선분이 있는 좌표를 기록했다.

그 후 정사각형의 4개의 꼭짓점이 모두 드래곤 커브의 일부인지의 판단은 좌표 (i,j) 기준 (i, j+1), (i+1, j), (i+1, j+1) 모두 true라면 해당 정사각형은 정답에 포함되는 정사각형이다.