[C++] 백준 2011 - 암호코드

문제 링크

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

2011번: 암호코드

 

숫자의 왼쪽에서 하나씩 보면서

1. 숫자가 0이 아니면 한가지의 방법이 생깁니다.

2. 이전 숫자와 합쳤을 때 26이하이면 한가지의 방법이 추가로 생깁니다.

 

이 때 1번의 조건이 맞으면 현재 숫자까지는 이전 숫자까지의 방법과 동일합니다.

2번의 조건도 맞게 된다면 현재 숫자의 두번째 전 숫자의 방법이 추가됩니다.

 

마지막 숫자 4를 기준으로 보면 4는 0보다 크기 때문에 이전인 2511 상태의 방법만큼이 추가되고

이전숫자 1과 합쳤을 때 14가 되고 26 이하이기 때문에 두 번째 전 251 상태의 방법이 추가됩니다.

 

따라서

1번 조건이 성립시 d(n) = d(n-1)

2번 조건 성립시 d(n) = d(n) + d(n-2) 로 정답을 구할 수 있습니다.

 

 

구현 코드