[BOJ] 11057. 오르막 수(DP 기초)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

이 문제는 쉬운 계단 수 문제와 약간(?) 비슷하다.

쉬운 계단 수에서는 아래 그림을 보고

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1] 라는 점화식을 생각할 수 있었다.

마찬가지로 DP정도 위 문제와 동일하게 풀 수 있다.

- dp[i][j]는 수의 길이 i, 오름차순을 이루는 수가 j 로 끝나는 수의 개수

- 길이가 i 인 수, 마지막이 j 로 끝나는 오름차순의 수의 개수

이렇게 방식은 동일한데 문제만 바꿔서 낼 수가 있다.

그러니 많은 문제를 풀어보는게 확실히 좋은 듯 하다.

쉬운 계단 수 문제를 풀고 나니까 이 문제의 점화식도 빠르게 발견할 수 있었다.

아래 그림을 보고

dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 라는 점화식을 떠올릴 수 있어야 한다.

#. Code

#include <cstdio>
#define mod 10007
int dp[1001][11];
 
int main(void)
{
    int n, i, j, res = 0;
    scanf("%d", &n);
 
    for (i = 0; i <= 9; i++)
        dp[1][i] = 1;
 
    for (i = 2; i <= n; i++) {
        dp[i][0] = 1;
 
        for (j = 1; j <= 9; j++) {
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
        }
    }
 
    for (i = 0; i <= 9; i++)
        res += dp[n][i];
 
    printf("%d\n", res % mod);
 
    return 0;
}

line 10) 직관적으로 구할 수 있는 작은 문제의 해를 미리 구해놓는다.

line 17) 점화식 적용!!

#. Other Code

#include <cstdio>
#define mod 10007
int dp[11] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
 
int main(void)
{
    int n, i, j;
    scanf("%d", &n);
 
    for (i = 2; i <= n; i++) {
        int tmp = 0;
 
        for (j = 1; j <= 10; j++) {
            tmp = tmp + dp[j];
            dp[j] = tmp % mod;
        }
    }
    printf("%d\n", dp[10]);
 
    return 0;
}

점화식을 알아내고 코드를 최적화시킨다면 이렇게 짤 수도 있다.

여기서 dp는 해당 길이의 수에서 마지막이 j로 끝나는 오름차순 수의 개수이다.

n이 1일 경우를 예로 들면 

1로 끝나는 오름차순 수, 1~2로 끝나는 오름차순 수, 1~3으로 끝나는 오름차순 수... 로 저장된다

line 3) 초기 한 자리 수의 경우 직관적인 문제에 대한 해

line 14) 마지막이 j로 끝나는 오름차순 수의 개수를 누적

line 15) 누적된 값을 dp[j]에 저장

line 18) 마지막으로 길이가 N인 수의 0~9로 끝나는 오름차순 수의 개수를 출력