드래곤 커브

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

삼성 코딩 테스트 보러 가서 풀지 못한 문제이다. 시뮬레이션 문제이다.

풀이

우선 규칙을 찾아야한다.

시작점이 (4,2), 첫 시작방향이 북쪽(1), 차원이 3차원을 그림으로 그려 확인해보자.

이를 숫자를 이용해 테이블로 나타내면 다음과 같다.

위의 테이블에서 알 수 있듯이, n차원의 요소들은 n-1차원의 요소들을 그대로 가지고, +1씩 더한 요소들을 추가적으로 가진다.

여기서 중요한 것은, 남쪽 방향(3)은 다음 차례에서 동쪽 방향(0)으로 추가된다

따라서 다음과 같은 플로우로 문제를 푼다.

1. 드레곤 커브의 개수 만큼 어레이리스트를 생성한다.
2. 바로 전 리스트 요소 복사하고 새로운 요소를 추가함으로써, i번째 어레이리스트를 setting 한다.
3. i번째 어레이리스트를 map에 그린다.
4. 2번과 3번의 작업을 모두 마치고, 직사각형의 개수를 count 한다.