백준 2688번 줄어들지 않아 [DP] :: 마이구미

이번 글은 백준 알고리즘 2688번 "줄어들지 않아" 문제를 다뤄본다.

핵심은 DP라고 불리는 동적계획법이다.

일단 문제를 보자.

어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다.

예를 들어, 1234는 줄어들지 않는다. 

줄어들지 않는 4자리 수를 예를 들어 보면 0011, 1111, 1112, 1122, 2223이 있다. 줄어들지 않는 4자리수는 총 715개가 있다.

이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수이다.

n이 주어졌을 때, 줄어들지 않는 n자리 수의 개수를 구하는 프로그램을 작성하시오.

각 자리 수에 따라 줄어들지 않는 경우의 수를 구하면 된다.

간단하게 나타내보자면 아래와 같다.

n = 1 -> 0,1,2,3,4,5,6,7,8,9 = 10개
n = 2 -> 00,01,02,03,04,05,06,07...... = 55개
n = 3 -> 000,001,002,003,004.......    = 220개
n = 4 -> 0000,0001,0002,0003.......  = 715개

모든 자리에서의 수는 0~9만을 생각하면 된다.

그렇다면 dp 배열을 만들어 보자.

dp[i][j] = i자리에 j값을 넣을 수 있는 경우의 수가 될 수 있다.

이 때 i는 1~64 j는 0~9가 된다.

2자리 수에서 0,1,2 가 들어가는 경우를 보자.

dp[2][0] = 00     // 2자리 수에서 0이 들어갈 수 있는 경우
dp[2][1]  = 01      // 2자리 수에서 1이 들어갈 수 있는 경우
dp[2][1]  = 11       // 2자리 수에서 1이 들어갈 수 있는 경우
dp[2][2] = 02     // 2자리 수에서 2이 들어갈 수 있는 경우
dp[2][2] = 12      // 2자리 수에서 2이 들어갈 수 있는 경우
dp[2][2]  = 22    // 2자리 수에서 2이 들어갈 수 있는 경우

그리고 3자리 수에서 2가 들어가는 경우를 보자.

dp[3][2] = 012
dp[3][2] = 112
dp[3][2] = 022
dp[3][2] = 002
dp[3][2] = 122
dp[3][2] = 222

규칙이 보이는가?

2자리 수에서 0,1,2가 들어가는 경우의 숫자 뒤에 2만 붙였을 뿐인데 줄어들지 않는 숫자가 되었다.

결론은 dp[3][2] = dp[2][0] + dp[2][1] + dp[2][2] 가 된다는 뜻이다.

점화식으로 표현하자면, dp[i][j] = sum( dp[i-1][k] )  [k <= j] 성립이 된다.

for(int i=2;i<65;i++) {
    long sum = 0;
    for(int j=0;j<10;j++) {

        dp[i][j] = dp[i-1][j] + sum;

        sum += dp[i-1][j];
    }   
}

어렵고 익히기가 쉽지 않은 동적계획법이지만 계속계속 연습하자.

전체 소스는 Github URL을 통해 확인하면 된다.

이만 안녕.

Github URL 소스

https://github.com/hotehrud/acmicpc/blob/master/dp/2688.java

백준 2688번 줄어들지 않아

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