[Java] 백준 11057 : 오르막 수

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

1.

무슨 문제인지는 모르겠지만 전에 풀었던 문제와 유사하다는 느낌을 받았다.

점화식 규칙을 찾으려고 공책에 $n=3$ 일 경우까지 모두 적어보았다.

 

 

2.

dp배열을 2차원으로 구성하는 것이 핵심이다.

행은 n을 나타내고 열은 0부터 9까지의 수를 나타내는데, 각 배열의 원소는 해당 열로 끝나는 숫자로 나타낼 수 있는 경우의 수이다.

 

위 그림은 $n=3$일 경우 만들어지는 dp 배열이다. 이를 점화식으로 나타내면 다음과 같다.

 

dp[i][j] = (dp[i - 1][j] + dp[i][j - 1])

 

 

왜 이렇게 점화식을 세웠는지 다음 그림을 통해 알아보자.

 

$(3, 2)$ 에서 주황색 부분은 $(2, 2)$의 원소 맨 앞에 $0$을 붙여준 것과 같다.

$(3, 2)$ 에서 파란색 부분은 $(3, 1)$의 원소를 $1$씩 증가시킨 것과 같다.

모든 경우의 수를 적으면서 규칙을 찾고 점화식을 세우는 것이 문제의 핵심이다.

 

 

3.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[][] dp = new int[n + 1][10];

        for (int i = 1; i <= n; i++) {
            dp[i][0] = 1;
            for (int j = 1; j < 10; j++) {
                if (i == 1) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 10007;
                }
            }
        }

        int answer = 0;
        for (int i = 0; i < 10; i++) {
            answer += dp[n][i];
        }
        System.out.println(answer % 10007);

        sc.close();
    }
}

 

 

4.

- dp배열을 1차원으로 만들려고만 하지 말고 2차원 배열로 구성하는 방법도 생각하자.

 

- 10,007로 나눠주라는 문제의 조건을 잊었다. 처음부터 적어놓고 잊지 말자.

 

[참고] http://bitly.kr/07MPIFsiF0O