백준 알고리즘 2193 문제 - 이친수

https://www.acmicpc.net/problem/2193

2193번: 이친수

 

문제는 백준 알고리즘 사이트를 참조하세요

 

먼저 분석과 설계를 하고 시작할게요

 

Pinary Number

 

1 - 0으로 시작하지 않는 수

2 - 1이 두번 연속으로 나오지 않는 수

 

를 이친수라고 하네요. 

 

문제에서 요구하는 것은1 부터 90까지 주어지는 N에 대해서 N자리 이친수의 개수를 구하는 거네요!

 

그럼 이 사실로부터 앞이 1이면 뒤는 무조건 0이어야하고, 앞이 0이면 뒤는 1 혹은 0이 올 수 있다는 것을 알 수 있겠네요 오호~

 

이것을 그림으로 표현하면

이렇게 표현할 수 있습니다.

 

그리고 구해야하는 정답이 이친수의 개수라고 했으므로 재귀를 이용하거나 배열을 사용한 동적 프로그래밍을 하는게 맞겠네요.

 

그런데 90번째 이친수를 재귀적으로 구하려면 시간이 초과되겠죠??

 

동적 프로그래밍을 합시다.

 

지금까지는 앞에서 뒤 방향으로 관찰했었는데요. 잘 보면 0은 0이나 1에서 올 수 있고, 1은 무조건 0에서 밖에 못 온다는 것을 알 수 있습니다.

 

빨간색 선으로 표시된 부분에서 새로운 경우의 수가 발생하는거죠.

 

이것을 재귀적으로 표현하면 다이나믹 프로그래밍이 완성됩니다.

 

pinary number[i][0] = pinary number[i - 1][0] + pinary number[i - 1][1];
pinary number[i - 1][1] = pinary number[i - 1][0];

 

마칩니다~