섹션 8 DFS, BFS - 7. 조합의 경우수(메모이제이션)

문제 설명

조합의 경우의 수는 보통 nCr = n! / (n-r)!r!의 공식으로 계산되지만 이번 문제는 재귀 호출과 메모이제이션을 통해 아래의 조합 점화식을 이용하여 nCr을 계산해야 한다.

---

입력 & 출력

입력

• 첫 줄: 두 자연수 n, r (3 ≤ n ≤ 33, 0 ≤ r ≤ n)

출력

• 조합값 nCr 출력

---

예제 입력 & 출력

예제 입력 1

 

5 3

예제 출력 1

 

10

예제 입력 2

 

33 19

예제 출력 2

 

818809200

---

해결 방법

nCr = (n-1)C(r-1) + (n-1)Cr

• 조합 점화식
• 이 식은 파스칼의 삼각형 원리 기반
• 메모이제이션을 통해 중복 계산 제거

---

코드 구현 (Java)

package partDfsBfs;

import java.util.Scanner;

public class Problem7 {
	static int[][] dy = new int[35][35];

	public int DFS(int n, int r) {
		if (dy[n][r] > 0) return dy[n][r]; // 메모이제이션
		if (n == r || r == 0) return 1;    // 종료 조건
		return dy[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r);
	}

	public static void main(String[] args) {
		Problem7 T = new Problem7();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int r = kb.nextInt();
		System.out.println(T.DFS(n, r));
		kb.close();
	}
}

---

코드 설명

1. 메모이제이션 배열

static int[][] dy = new int[35][35];

• dy[n][r]에 nCr 값을 저장하여 중복 계산 방지

2. 종료 조건

if (n == r || r == 0) return 1;

• 조합 기본 성질: nCn = 1, nC0 = 1

3. 점화식 적용

dy[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r);

• 재귀적으로 nCr 계산
• 이미 구한 값은 dy[n][r]에 저장하여 재사용

---

시간 복잡도 분석

• 메모이제이션 없이 순수 재귀로 구현하면 각 호출이 두 번씩 분기되므로 전체 호출 트리는 이진 트리 형태 → O(2ⁿ)
• 메모이제이션을 사용한 재귀는 중복 계산을 방지하므로 실제로 계산되는 상태는 dy[0][0]부터 dy[n][r]까지 최대 약 n × r개
  → 시간 복잡도: O(n × r)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런