[백준/BOJ] 2193번: 이친수 ( 동적 프로그래밍 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/2193 풀이이 문제는 숫자의 자릿수가 주어졌을 때, 만들 수 있는 이친수( pinary number )의 개수를 구하는 문제입니다. 적은 자릿수의 이친수로부터 더 큰 자릿수의 이친수를 만드는 과정을 생각해 보면 규칙성을 만들어 볼 수 있습니다. 먼저, 간단히 4 자릿수 이친수를 만든다고 해봅시다.그럼, 3 자릿수 이친수의 끝 부분에 0을 붙이면 이친수의 규칙을 어기지 않고도 4 자릿수 이친수를 만들 수 있습니다. 그런데, 3 자릿수 이친수의 끝 부분에 1은 붙일 수 없습니다. 이렇게 해서 만들어진 4 자릿수의 숫자는 이친수가 아닐 수도 있기 때문입니다. ( 예, 1011 ) 그럼, 1로 끝나는 이친수는 만들 수 없는 걸까요..