백준 15992번
https://www.acmicpc.net/problem/15992
DP 문제이다.
메모이제이션을 사용해서 TopDown으로 구현했다.
private static int topDown(int n, int m, int currentNumber) {
if (n == 0 && m == 0) return 1;
if (n < 0 || m < 0 || currentNumber <= 0) return 0;
if (memo[n][m] != -1) return memo[n][m];
memo[n][m] = (topDown(n - currentNumber, m - 1, 3) + topDown(n, m, currentNumber - 1)) % MOD;
return memo[n][m];
} // End of topDown()
TopDown으로 N
과 M
의 값으로 시작해서 아래로 내려간다.
값을 선택하지 않고 그대로 진행하는 경우, topDown(n - currentNumber, m - 1, 3)
으로 n
을 선택한 값 만큼 빼주고, m
의 사용횟수도 1을 빼준다.
값을 변경하고 사용하지 않는 경우, topDown(n, m, currentNumber - 1)
로 currentNumber
만 그대로 -1을 해준다.
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
// input
private static BufferedReader br;
// variables
private static final int MOD = 1_000_000_009;
private static int N, M;
private static int[][] memo = new int[1001][1001];
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for (int[] t : memo) {
Arrays.fill(t, -1);
}
int T = Integer.parseInt(br.readLine());
while (T-- > 0) {
input();
bw.write(solve());
}
bw.close();
} // End of main
private static String solve() {
StringBuilder sb = new StringBuilder();
sb.append(topDown(N, M, 3)).append('\n');
return sb.toString();
} // End of solve()
private static int topDown(int n, int m, int currentNumber) {
if (n == 0 && m == 0) return 1;
if (n < 0 || m < 0 || currentNumber <= 0) return 0;
if (memo[n][m] != -1) return memo[n][m];
memo[n][m] = (topDown(n - currentNumber, m - 1, 3) + topDown(n, m, currentNumber - 1)) % MOD;
return memo[n][m];
} // End of topDown()
private static void input() throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
} // End of input()
} // End of Main class