N으로 만들기
면접 대비시간 제한1초메모리 제한256 MB
새 숫자를 왼쪽이나 오른쪽 끝에 붙여 가며 N을 만드는 방법의 수를 센다.
문제
준하는 노트에 수를 적다가 수가 만들어지는 방식을 깨달았다.
처음에 어떤 숫자 하나를 적고 만들어진 수의 왼쪽이나 오른쪽에 숫자를 계속 붙이면 어떤 수 N이든 만들 수 있다는 것이다.
다시 말해 어떤 수 N을 만들기 위해서는, 처음에 어떤 숫자를 하나 적고 아래의 두 가지 행동을 반복한다.
- 수의 왼쪽에 숫자를 하나 적는다.
- 수의 오른쪽에 숫자를 하나 적는다.
준하는 어떤 수 N을 만드는 방법의 수가 몇 가지인지 궁금해졌다. 이를 알아내는 프로그램을 작성해주자. 숫자를 적는 과정에서 나온 수가 순서대로 모두 같다면 같은 방법이다.
단, 숫자를 적는 과정에서 수는 0으로 시작할 수 있다.
입력
음이 아닌 정수 N이 주어진다. (0 ≤ N ≤ 10,000,000)
출력
N을 만드는 방법의 수를 출력한다.