트랩
시간 제한2초메모리 제한512 MB
격자 위에서 (0,0)에서 오른쪽으로 출발하는 n개의 단위 구간으로 이루어진 자기회피 보행 중, 다음 구간을 추가하면 자기교차가 생겨 더 나아갈 수 없는 보행의 수를 센다.
문제
정수 좌표를 가진 격자점들을 잇는 점의 나열을 생각한다. 나열에서 이웃한 두 점은 길이 1인 가로 또는 세로 선분 하나를 이룬다. 이런 나열을 워크(walk)라고 부르자.
n개의 선분으로 이루어진 워크 중에서 자기 자신과 교차하지 않는 것, 즉 워크 안의 선분들이 서로 만나지 않고 닿지도 않으며 (이웃한 두 선분은 예외) 스스로를 피하는 워크를 생각하자. 또한 워크의 첫 번째 선분은 좌표 (0,0)과 (1,0)을 잇고, 첫 번째 세로 선분은 위쪽을 향해야 한다.
n걸음 뒤에 갇힌(trapped) 자기 회피 워크의 개수를 구하는 프로그램을 작성하시오. 갇힌 워크란 다음 (n + 1)번째 선분을 추가하면 자기 교차가 일어나 더 이상 진행할 수 없는 워크이다.
입력
정수 n이 주어진다.
출력
구하고자 하는 개수를 정수로 출력한다.
제한
- 0 < n < 27
힌트
두 워크는 (0,0) (1,0) (2,0) (2,1) (2,2) (1,2) (0,2) (0,1) (1,1)과 (0,0) (1,0) (1,1) (2,1) (3,1) (3,0) (3, -1) (2, -1) (2,0)이며, 그림에 나타나 있다.
