백준 1038번 감소하는 수

문제

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

문제풀이

사용한 알고리즘 : DP

(0) 주의

  감소하는 수는 최대 10자리, 9876543210 입니다. (참고로 9876543210 은 1022번째 감소하는 수입니다. 입력된 N>1022 이면 -1 출력하면 됩니다.)
 또한, k 자리의 감소하는 수는 k-1부터 시작 가능합니다.
 예를 들어 4자리의 감소하는 수는 3부터 시작 가능합니다. ( 3210 )

(1) 생각

 저는 편의를 위해 '개수'를 따라가려고 0을 1번째 감소하는 수라고 생각하였습니다.
 0 : 1번째 감소하는수 , 1 : 2번째 감소하는 수, 2: 3번째 감소하는 수, ...
 그러므로 입력으로 N 이 들어오면 N+1 번째 감소하는 수를 찾을 것입니다.
 예를 들어 입력된 N=2 일 경우, 3번째 감소하는 수를 찾을 것이고, 답은 2 입니다.

(2) 코드 6~9

 ' dp[k][x] : k 자리의 x로 시작하는 감소하는 수의 개수' 라고 설정하였습니다.
 예를 들어 dp[3][3] = 3 입니다. ( 310, 320, 321 )
 ' S[k] = k 자리의 감소하는 수' 라고 설정하였습니다.
 S[1] := 1자리 감소하는 수 = 10,  S[2] := 2자리 감소하는 수 = 45, ... 입니다.

(3) 코드 34~48

 위에서 설정한 것을 토대로 dp 와 S 값을 각각 구해줍니다.
 점화식은 dp[k][x] = dp[k-1][0] + ... + dp[k-1][x-1], S[k] = dp[k][0] + ... + dp[k][9] 입니다.
 다만 k 자리수의 감소하는 수는 k-1부터 시작한다는 점을 이용하면 좀 더 압축 가능합니다.

(4) 코드 50~56

 우선 앞서 밝힌 바와 같이, N이 입력되면 N+1 번째 수의 자리 수를 찾을 것입니다.
 1자리부터 S[k]로 차례로 탐색하면서,
    1. S[k] >= N+1이면 구하고자 하는 N+1 번째 수는 k 자리라는 것을 알 수 있습니다.
    2. S[k] < N+1 이면 N+1 = N+1 - (S[k]) 를 취해줍니다.

 예를 들어 입력이 18로 들어오면 19 번째 수를 찾습니다.
 S[1] < 19 이므로 19번째 수는 1자리가 아닙니다.
 따라서 2자리 감소하는 수 중 19 - 10 = 9 번째 수를 찾아주면 되는 것입니다.
 10, 20, 21, 30, 31, 32, 40, 41, 42 순이므로 42가 답이 됩니다.

(5) 코드 12~26

 k 자리 수의 감소하는 수 중 cnt 번째 수를 찾는 함수입니다.
 예를 들어 2자리 수 중 9 번째 수를 찾는다 생각하면 다음과 같이 탐색하게 됩니다.
 ( k자리 수는 k-1 부터 시작할 수 있음을 항상 생각해줍니다. )

 2자리 수중 9번 째 수를 찾으면,
 1. dp[2][1] = 1 < 9 이므로 1로 시작하는 2자리 수는 답이 될 수 없습니다. 9 -1 = 8
 2. dp[2][2] = 2 < 8 이므로 2로 시작하는 2자리 수는 답이 될 수 없습니다. 8 - 2 = 6
 3. dp[2][3] = 3 < 6 이므로 3으로 시작하는 2자리 수는 답이 될 수 없습니다. 6 - 3 = 3
 4. dp[2][4] = 4 >= 3 이므로 4로 시작하는 2자리 수가 답이 됩니다.
 4로 시작하는 2자리 감소하는 수 중 3번째 수를 찾아줍니다.
 즉, 1자리 수 중 3번째 수를 찾아주면 됩니다.

 위와 같은 방법으로 1자리 수 중 3번째 수를 찾으면,
 1. dp[1][0] = 1 < 3 이므로 0으로 시작하는 1자리 수는 답이 될 수 없습니다. 3 - 1 = 2
 2. dp[1][1] = 1 < 2 이므로 1로 시작하는 1자리 수는 답이 될 수 없습니다. 2 - 1 = 1
 3. dp[1][2] = 1 >= 1 이므로 2로 시작하는 1자리 수가 답이 됩니다.
 따라서 답은 42 가 되는 것입니다.

 쓰다 보니 굉장히 지저분한 풀이가 된 것 같네요...