[자바] 백준 11057번 오르막 수. 2021-08-04

우선 어려웠다. 애초에 dp 배열을 1차원으로 구하면 될 줄 알았는데  그게 아니였다. 그리고 배열의 기준을 첫번쨰 자리부터 차근차근 올라가면서 앞 자리수보다 크거나 같은 수를 구하는 방식이 아니라, 미리 맨 마지막 자리에 올 수를 정해놓고, 앞 자리수에 올수 있는 수를 한정해주는 방법을 쓴다. 그래고 매우 어려운 것이, 우선 난 dp문제를 풀때의 철칙이 1. dp[i]=num의 정의, 2. dp[N]과 dp[N-1]의 관계를 파악해서 프로그래밍을 하였는데 그래서 난 계속 1차원 배열로 풀려고 했었다.

그런데 이젠 dp 배열이 2차원으로 푸는 문제인지 아닌지 0순위로 판단후, 파악해야겠다.

우선 이 문제에서 dp[i][j]=num 의 정의는 "i 번째 자리수에서 맨 마지막 자리에 오는 숫자가 j 일때 가능한 오르막 수의 갯수: num" 으로 정의했다. 그럼 자연스럽게 i 의 범위는 1부터 입력받은 자리수 N 까지 가 되고, j의 범위는 숫자 한자리의 범위이니 0~9까지 이다.

int[][] dp=new int[N+1][10];

 일단 1번째 자리수 부터 정하고 올라가는 방식이 아니라 마지막 자리 숫자를 한정해버리고 끼워맞추듯 구하는 방식이라 너무 어려웠다.

dp[N][j] 와 dp[N-1][j] 의 관계를 구하려면  각 행이 지날수록 둘 사이 어떤 규칙이 존재하는지 파악해야한다.

우선 표를 그려보면,

N	0	1	2	3	4	5	6	7	8	10
1	1	1	1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7	8	9	10
3	1	3	6	10	15	21	28	36	45	55

이제 규칙이 보인다. 바로 전 행의 0부터 해당 자릿수까지의 더한 값이다. 빨간색 1,2,3 을 더한 값이 6.

점화식으로 풀어쓰면

dp[N][j]=dp[N-1][0]+dp[N-1][1]+dp[N-1][2]+...dp[N-1][j] 이렇다.

이런 규칙이 나오는 이유는 직접 내가 하나하나 해보니, 마지막 자리 기준이므로, 앞전 자릿수의 모든 경우를 다 더한 값이여야 된다는 것을 알게 되었다. 직접해보면 나온다.

그래서 점화식을 바탕으로 프로그래밍을 하면 이렇게 된다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int N = s.nextInt();

        int[][] dp=new int[N+1][10];
        for (int i = 0; i < 10; i++) {
            dp[1][i]=1;
        }
        for(int i=2;i<=N;i++){
            for (int j = 0; j < 10; j++) {
                int sum=0;
                for (int k = 0; k <= j; k++) {
                    sum+=dp[i-1][k];
                }
                dp[i][j]=sum%10007;
            }
        }
            int sum=0;
        for (int i = 0; i < 10; i++) {
            sum+=dp[N][i];
            sum%=10007;
        }
        System.out.println(sum);


    }


}

공부시간 1시간.

순공부시간 30분.

오늘 오전엔 또 병원 가느라 공부 하나도 못했고, 오후에도 집중력이 떨어졌는지, 공부가 잘 안됬다. ㅠㅠ 그래도 그전보단 2차원 dp 배열이 쓰이는 문제를 빨리 이해한거 같다.