두 가지 방식(Top-Down, Bottom-Up)으로 풀이했다.
Bottom-Up은 for문을 돌면서 DP에 담길 모든 값을 계산해야 한다. Top-Down은 재귀 호출을 하면서 필요한 값만 계산한다. 계산하는 횟수의 차이가 크다면 Top-Down이 유리할 수 있다. 하지만 그 차이가 크지 않다면 Top-Down이 Method를 재귀 호출하면서 쌓이는 System Stack 때문에 Bottom-Up이 더 유리할 수 있다.
① 기저 조건 : if(맨 마지막까지 내려갔으면) 문제에서 주어진 초기 값 넘겨주기
② if(이미 계산되었다면) 바로 return
③ if(아직 계산되지 않았다면) 계산하기
④ DP 배열에 값을 저장함과 동시에 return
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main_2775_TopDown {
static int[][] dp;
static int K, N;
public static void main(String[] args) throws NumberFormatException, IOException {
// B1 부녀회장이 될테야
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int t = 0; t < T; t++) {
K = Integer.parseInt(br.readLine());
N = Integer.parseInt(br.readLine());
dp = new int[K + 1][N + 1];
for (int i = 1; i <= K; i++) {
int sum = dp[i - 1][0];
for (int j = 0; j <= N; j++) {
sum += dp[i - 1][j];
dp[i][j] = sum;
}
}
rec(K, N);
System.out.println(dp[K][N]);
}
}
private static int rec(int k, int n) {
// 기저 조건
if (k == 0) {
return n;
}
// 값이 있으면 계산하지 않고 바로 넘겨주기
if (dp[k][n] != 0) {
return dp[k][n];
}
// 값이 없으면 계산하기
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += rec(k - 1, i);
}
// 배열의 값을 저장함과 동시에 리턴하기
return dp[k][n] = sum;
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main_2775_BottomUp {
public static void main(String[] args) throws NumberFormatException, IOException {
// B1 부녀회장이 될테야
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int t = 0; t < T; t++) {
int K = Integer.parseInt(br.readLine());
int N = Integer.parseInt(br.readLine());
int[][] dp = new int[K + 1][N + 1];
for (int i = 0; i <= N; i++) {
dp[0][i] = i;
}
for (int i = 1; i <= K; i++) {
int sum = dp[i - 1][0];
for (int j = 0; j <= N; j++) {
sum += dp[i - 1][j];
dp[i][j] = sum;
}
}
// for (int i = 0; i <= K; i++) {
// for (int j = 0; j <= N; j++) {
// System.out.print(dp[i][j] + " ");
// }
// System.out.println();
// }
System.out.println(dp[K][N]);
}
}
}