[BOJ - JAVA] 11057 - 오르막수(DP)

[BOJ - JAVA] 11057 - 오르막수(DP)

반응형

# 주소

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

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*; public class Main{ public static void main(String[] args){ Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int[][] dp = new int[n+1][10]; for(int i = 0; i < 10; i++){ dp[0][i] = 1; } for(int i = 1; i < n+1; i++){ for(int j = 0; j < 10; j++){ for(int k = j; k < 10; k++){ dp[i][j] += dp[i-1][k]; dp[i][j] %= 10007; } } } System.out.println(dp[n][0] % 10007); } }

점화식 문제입니다. 제가 점화식이 많이 약해서 푸는데 다른 분들의 아이디어를 얻었습니다.

점화식은 특히 2차원 배열을 이용해서 푸는 것이 가장 어렵다고 느껴집니다. 이것 역시 표로 이해하는 것이 빠릅니다.

0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 10 9 8 7 6 5 4 3 2 3 55 45 36 28 21 15 10 6 3 4 220 165 120 84 56 35 20 10 4

자 보시면 옆에 행 하나가 잘렸는데 이렇게만 봐도 확연히 눈에 잘 보입니다.

그러니까 dp[4][1] = dp[3][1] 부터 dp[3][10]까지 다 더한 값입니다.

그러므로 dp[i][1]의 자리에는 바로 위에 있는 행의 값을 전부 다 더한 값입니다.

또한 가장 마지막에 있는 열의 크기는 1인데 열이 잘려서 나오진 않는다는 점 양해부탁드립니다..

한편 그 외의 값들은 단순한 뺄셈을 통하여 유추할 수 있습니다.

즉 dp[3][2]로 예를 든다면 dp[3][1] - dp[2][2]를 통해 dp[3][2]가 무엇인지 짐작할 수 있습니다. 따라서 모든 dp의 값들은 바로 윗 행부터 제 10열까지 값을 전부 더한 것이 됩니다.

그러므로 n의 오르막 수 값은 dp[n+1][0]의 값이므로 출력해주시면 됩니다.

반응형

from http://codingrapper.tistory.com/64 by ccl(A) rewrite - 2021-10-28 02:01:27