그랬었습니다

정답률이 30퍼도 안되는 문제다. 근데 솔직히 정답률 더 높은 계단 오르기나 1로 만들기 문제보다 쉽게 느껴졌다. 왜지..? 요즘 동적 계획법 문제를 많이 풀어서 익숙해졌나? 아무튼.. 이 문제는 의외로 간단하다. 중복을 생각할 필요가 없다. 대신 예외를 생각해야한다. 1에서 파생되는 수는 10, 12가 있다. 2에서는 21, 23이 있다. 등등.. 그럼 두 자리 숫자로 넘어가보자. 10에서 파생되는 수는? 101뿐이다. 89에서 파생되는 수는? 898뿐이다. 나머지는 모두 끝 자리 숫자에 1을 빼고 더하는 두 가지 경우가 나온다. 복잡하게 생각하지 말고 맨 끝자리만 보면 된다. 길이 N인 계단 수 중에서 끝자리가 0인 수의 개수는? 길이 N - 1인 계단 수 중에서 끝자리가 1인 수의 개수와 같다. 끝..