[BOJ] 부녀회장이 될테야 # 2775

두 가지 방식(Top-Down, Bottom-Up)으로 풀이했다.

Top-Down VS Bottom-Up

Bottom-Up은 for문을 돌면서 DP에 담길 모든 값을 계산해야 한다. Top-Down은 재귀 호출을 하면서 필요한 값만 계산한다. 계산하는 횟수의 차이가 크다면 Top-Down이 유리할 수 있다. 하지만 그 차이가 크지 않다면 Top-Down이 Method를 재귀 호출하면서 쌓이는 System Stack 때문에 Bottom-Up이 더 유리할 수 있다.

(1) Top-Down

Top-down 방식이란?

• 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식이다.
• 보통 재귀 호출을 통해서 구현한다.
• 하향식 접근법이라고도 한다.

구성

① 기저 조건 : 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;
	}

}

(2) Bottom-Up 풀이

Bottom-Up 방식이란?

• 가장 작은 문제들부터 답을 찾아가면서 전체 문제의 답을 구하는 방식이다.
• 보통 반복문을 이용해 구현한다.
• 상향식 접근법이라고도 한다.

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]);
		}
	}

}