백준 15685 드래곤 커브

일단 규칙을 좀 생각해봤다.

1. k세대는 (k - 1)세대를 시계방향으로 90도 돌린 후에 (k - 1)세대의 끝점에 90도 돌린 것의 끝점을 붙이게 된다. 그래서 (k - 1)세대의 역방향으로 새로운 길이 추가된다고 볼 수 있다.
역방향은 x, y방향은 각각 유지하면서 부호만 바꿔주면 된다.

2. 그리고 시계방향으로 90도 돌릴 경우 각 이동 규칙은...
y방향 음수 -> x방향 양수
y방향 양수 -> x방향 음수

x방향 음수 -> y방향 음수
x방향 양수 -> y방향 양수

일단 x -> y, y -> x 가 되고, y방향의 경우만 부호가 바뀐다.
(x, y) -> (-y, x) 로 해주면 된다.

규칙 1과 2를 이용해서 점을 찍고나서
모든 점을 돌면서 각 점마다 오른쪽, 아래 방향으로 1 * 1 정사각형을 구성하는 꼭지점이 있는지 확인해 보면서 1 * 1 정사각형의 개수를 세면될 것 같다.

규칙 1과 2를 이용해서 점을 찍는 부분의 구현이 좀 까다롭다.
먼저 k세대를 구하기 위해서 0세대부터 시작을 한다.
i세대의 이동 방향을 reverse해주고, 그 값을 90도 돌려주는 작업을 해준다.
그리고 i세대의 끝에 이어 붙인다. 그러면 (i+1)세대의 이동방향이 완성된다. 각 이동 방향은 pair(x, y)로 묶어서 vector에 이어붙일 것이다.

이렇게 k세대의 이동방향을 구하면 그를 토대로 점을 check해준다.

결국 이렇게 구현해서 AC를 받았다.
코드가 꽤 길어졌는데, 맞은 사람을 보니 짧게 구현한 사람도 꽤 있다. 이해는 잘 안 가지만, 좀 더 간단히 구현할 수 있는 방법이 있는 것 같다... 더 열심히 해야겠다.