BOJ_S5_1010

📁 [S5_1010] 다리 놓기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static StringTokenizer st;
	static int L, R;
	// 동적 계획법
	static int[][] dp = new int[30][30];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		// 테스트 케이스 입력
		int TC = Integer.parseInt(br.readLine());

		for (int t = 0; t < TC; t++) {
			st = new StringTokenizer(br.readLine(), " ");
			// 왼쪽 사이트 수
			L = Integer.parseInt(st.nextToken());

			// 오른쪽 사이트 수
			R = Integer.parseInt(st.nextToken());
			
			//출력
			sb.append(combination(R, L)).append("\n");
		}
		System.out.println(sb);
	}
	
	// nCr 계산
	static int combination(int n, int r) {
		
		// 이미 풀었던 것일 경우 재활용
		if(dp[n][r]>0) {
			return dp[n][r];
		}
		
		// 기저조건
		if(r == 0 || n == r) {
			return dp[n][r] = 1;
		}
		
		// 재귀 돌리면서 값 메모이제이션 , 
		// R , L 에서 시작하기 때문에 - 사용
		return dp[n][r] = combination(n-1, r-1) + combination(n-1, r);
	}
}

🤔 나의 생각

굉장히 풀이가 보이는 문제였지만 제일 고생한 문제..
정말.. 처음에는 당연히 조합인 줄 알고 조합을 재귀로 했는데 실패하고..
nCr 조합 연산식으로 했는데도 StackOverFlow가 발생하고..
결국 발견한 것은 dp.. 재귀를 돌리면서 메모제이션 하는 것이 키 포인트 였던 것 같다.
어떤 분은 조합 점화식을 사용하여 계산하였는데 StackOverFlow가 안 발생하고 잘 되었다.
점화식도 괜찮은 방법 같다 !!