[알고리즘/dp] 백준 2193번 이친수

문제

풀이

• 0으로 시작하면 안된다. => 첫째 자리는 반드시 1이어야 한다.
• 1이 두번 연속으로 나타나면 안된다. => 1의 앞,뒤에는 반드시 0이어야 한다.

이 두 조건을 통해, N이 1보다 클 경우 반드시 앞 두자리는 1, 0 이 차례로 와야 한다.

앞 1, 0를 고정으로 두고 맨 뒤는 0, 1일 때 각 경우의 수를 구하면 된다.

N=1 일 경우, [1] => 가능한 수 1개

N=2 일 경우, [1][0] => 가능한 수 1개 = 끝이 0일 경우 1개 + 끝이 1일 경우 0개

N=3 일 경우, [1][0][0], [1][0][1] => 가능한 수 2개 = 끝이 0일 경우 1개 + 끝이 1일 경우 1개

N=4 일 경우, [1][0] 0 0, [1][0] 1 0,  [1][0] 0 1 => 가능한 수 3개 = 끝이 0일 경우 2개 + 끝이 1일 경우 1개

N=5 일 경우, [1][0] 0 0 0, [1][0] 1 0 0, [1][0] 0 1 0, [1][0] 0 0 1, [1][0] 1 0 1 => 가능한 수 5개 = 끝이 0일 경우 3개 + 끝이 1일 경우 2개

...

N을 하나씩 늘려 가면서 나열해보면 규칙이 보인다.

위의 예시에서 N=5일 때 끝자리 수가 0일 경우, 맨 앞 1,0과 맨 뒤 0을 제외한 중간 수들이

N-1인 N=4일 때의 맨 앞 1,0 이후 수와 동일하다.

끝자리 수가 1일 경우, N-1인 N=4일 때의 맨 뒤가 0일 경우의 1,0 이후 수와 동일하다.

if 맨 뒤가 0이면

  N일 때 맨 뒤가 0일 경우의 수 = N-1의 맨 뒤가 0일 경우의 수 + N-1의 맨 뒤가 1일 경우의 수

else if 맨 뒤가 1이면

  N일 때 맨 뒤가 1일 경우의 수 = N-1의 맨 뒤가 0일 경우의 수

최종적으로 N일 때 모든 이친수는 맨 뒤가 0, 1일 경우의 수를 모두 더한 값이 된다.

아래 코드를 보면 조금 더 간단하게 표현했다.

코드