비밀번호
면접 대비시간 제한1초메모리 제한1024 MB
3x3 격자에서 K가 적힌 칸에서 시작해 모든 칸을 한 번씩만 지나는 경로의 수를 센다.
문제
쿠는 자리 비밀번호를 정하려고 한다. 비밀번호 버튼은 아래와 같이 생겼다.
쿠가 만들고 싶은 비밀번호의 조건은 아래와 같다.
- 가장 먼저 가 적힌 버튼을 눌러야 한다.
- 이후 직전에 누른 버튼과 상하좌우로 인접한 버튼을 눌러야 한다.
- 각 버튼을 한 번씩만 눌러야 하며, 모든 버튼을 눌러야 한다.
가 적힌 버튼에서 비밀번호를 누르기 시작할 때 만들 수 있는 서로 다른 비밀번호의 개수를 구해보자.
입력
쿠가 비밀번호를 가장 먼저 누르는 버튼에 적힌 수 가 주어진다.
출력
가 적힌 버튼에서 비밀번호를 누르기 시작할 때, 만들 수 있는 서로 다른 비밀번호의 개수를 출력한다.
힌트
두 버튼이 인접해 있다는 것은 두 버튼이 변을 공유한다는 것을 의미한다.