[백준/DP] 11057번 오르막 수 (JAVA)
11372 단어 알고리즘백준ProblemSolvingProblemSolving
문제
풀이
dp[i][j]
:i
자리 수의 마지막 숫자가j
일 때의 오르막 수의 개수
i-1
길이의 오르막 수의 맨 뒤에 숫자 j
를 추가해가는 방식으로 dp[i][j]
배열을 채워나간다. 이 때, countAddable()
은 upperBound
이하의 숫자를 마지막 숫자로 갖는 i-1
길이의 오르막 수의 개수를 구한다.
최종 결과로는 dp[n][0]
부터 dp[n][9]
까지의 합을 구하면 정답이다.
코드
import java.io.*;
public class Main {
private static final int MAXIMUM = 1000;
private static final int MOD = 10007;
private static final int NUMBERS = 10;
private static int n;
private static int[][] dp = new int[MAXIMUM + 1][NUMBERS];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(br.readLine());
dp();
bw.append(String.valueOf(sum(dp[n])));
br.close();
bw.close();
}
private static void dp() {
for (int i = 0; i < NUMBERS; i++) dp[1][i] = 1;
for (int i = 2; i <= n; i++)
for (int j = 0; j < NUMBERS; j++)
dp[i][j] = countAddable(dp[i - 1], j) % MOD;
}
private static int countAddable(int[] arr, int upperBound) {
int count = 0;
for (int i = 0; i <= upperBound; i++) count = (count + arr[i]) % MOD;
return count;
}
private static int sum(int[] arr) {
int sum = 0;
for (int val : arr) sum = (sum + val) % MOD;
return sum;
}
}
Author And Source
이 문제에 관하여([백준/DP] 11057번 오르막 수 (JAVA)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jwkim/dp-11057저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)