[백준] 15685 드래곤 커브

0세대: 1

1세대: 1 2

2세대: 1 2 3 2

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

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

...

---

드래곤 커브의 시작 지점과 방향, 세대가 주어지며 드래곤 커브는 세대에 따라 확장된다. 네 꼭지점이 모두 드래곤 커브에 포함되는

1 * 1 크기의 셀 개수를 구하는 문제이다.

 

처음 문제를 풀 경우 세대마다 드래곤 커브를 구하고 이를 90도 회전하는 알고리즘을 생각할 수 있다. 하지만 이러한 알고리즘을 작성하면 매우 복잡해진다. 대신 드래곤 커브의 방향에서 규칙을 찾으면 문제가 간단해진다. 세대에 따른 선분의 방향을 구하면 아래와 같다.

 

→(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 
...

 

 

N 세대의 방향은 N-1 세대의 역방향 원소에 k 에 대해 (k+1) % 4의 값이 추가되는 것을 알 수 있다. 이렇게 구한 방향을 시작 지점에 대해 적용하면 문제를 해결할 수 있다.

 

Python