[백준 10844] 쉬운 계단수 풀이노트

위 로고를 누르면 해당 문제로 이동합니다.

1차 풀이 (2018-08-07, 1988 KB, 0 MS)

 최적부분 구조에 눈치채자. 

첫번째가 first로 시작하고, 전체가 n자리인 수를 살펴보자.

n	n-1	n-2	...	1	0
first

first가 이미 정해져있기 때문에,

n-1에는 first+1 또는 first-1 밖에 올 수 없다.

따라서 원래문제는 다음과 같은 부분문제로 나뉜다.

• 첫번째가 first+1로 시작하고, 전체가 n-1 자리인 계단수의 개수는?

• 첫번째가 first -1로 시작하고, 전체가 n-1 자리인 계단수의 개수는?

위의 부분문제와 원래문제는 독립적이므로 최적부분 구조로 볼 수 있다.

최적부분 구조는 동적 계획법으로 풀 수 있다.

적당한 메모이제이션을 사용하면 성능향상도 가능하다.

 1자리수도 계단수인가? 

예제 입출력을 보면 알 수 있다.

자리수가 1일 때, 계단수의 수는 9라고 알려주고 있다.

따라서 0이 아닌 1자리수는 계단수이다.

 0과 9 사이를 넘어가도 계단수인가? 

123, 456과 같은 수는 계단수임이 자명하지만,

901, 109는 계단수일까?

문제를 조금만 유의깊게보면 알 수 있다.

각 자리수의 차이가 1인 것이 계단수라고 정의하고 있다.

0과 9는 차이가 9 이므로 

0→9 또는 9→0은 계단수가 될 수 없다.