섹션 8 DFS, BFS - 8. 수열 추측하기

문제 설명

가장 윗줄에 1부터 N까지의 숫자 중 서로 다른 N개의 숫자가 한 개씩 적혀 있고, 그 아래줄부터 위 두 수를 더한 값이 저장되는 방식으로 삼각형을 만든다. 예를 들어 N=4이고 윗줄이 3 1 2 4이면 다음과 같다.

3  1  2  4
  4  3  6
   7  9
    16

 

가장 아랫줄의 값 F가 주어질 때 윗줄에 어떤 숫자를 배치해야 이 삼각형의 최하단 값이 F가 되는지 구하는 문제이다.
답이 여러 개인 경우 사전순으로 가장 앞서는 배열을 출력한다.

---

입력 & 출력

입력

• 첫 줄: 두 개의 정수 N, F (1 ≤ N ≤ 10, F ≤ 1,000,000)

출력

• 조건을 만족하는 수열을 사전순으로 출력 (공백 구분)

---

예제 입력 & 출력

예제 입력

 

4 16

예제 출력

 

3 1 2 4

---

해결 방법

파스칼의 삼각형 구조 활용

맨 마지막 줄의 수는 맨 윗줄의 숫자 각각에 파스칼 삼각형의 조합 계수를 곱한 합으로 계산된다.

F = p[0]*C(n-1,0) + p[1]*C(n-1,1) + ... + p[n-1]*C(n-1,n-1)

• 여기서 p[i]는 맨 윗줄의 수열의 i번째 수
• C(n-1, i)는 이항계수

---

해결 순서

1. C(n-1, i) 조합 계수 배열 b[]를 미리 구한다.
2. 1부터 N까지의 수 중에서 중복 없이 순열을 구성한다.
3. DFS로 순열을 탐색하며, 현재 수열 × 조합값의 합이 F인지 확인
4. 조건을 만족하면 출력하고 탐색 종료 (사전순으로 가장 앞선 순열)

---

예제로 공식 이해하기

예제 입력이 N = 4, F = 16일 때 정답 수열 중 하나는 p = [3, 1, 2, 4]이다. 이 수열을 공식에 대입하면 다음과 같이 계산된다:

F = 3*C(3,0) + 1*C(3,1) + 2*C(3,2) + 4*C(3,3)
  = 3*1 + 1*3 + 2*3 + 4*1
  = 3 + 3 + 6 + 4
  = 16

---

코드 구현 (Java)

import java.util.Scanner;

public class Problem8 {
	static int[] b, p, ch;
	static int n, f;
	boolean flag = false;
	int[][] dy = new int[35][35];

	public int combi(int n, int r) {
		if (dy[n][r] > 0) return dy[n][r];
		if (n == r || r == 0) return 1;
		return dy[n][r] = combi(n - 1, r - 1) + combi(n - 1, r);
	}

	public void DFS(int L, int sum) {
		if (flag) return; // 사전순 먼저 발견 시 종료
		if (L == n) {
			if (sum == f) {
				for (int x : p) System.out.print(x + " ");
				flag = true;
			}
		} else {
			for (int i = 1; i <= n; i++) {
				if (ch[i] == 0) {
					ch[i] = 1;
					p[L] = i;
					DFS(L + 1, sum + p[L] * b[L]);
					ch[i] = 0;
				}
			}
		}
	}

	public static void main(String[] args) {
		Problem8 T = new Problem8();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		f = kb.nextInt();
		b = new int[n];      // 조합계수
		p = new int[n];      // 순열 저장
		ch = new int[n + 1]; // 중복 체크

		for (int i = 0; i < n; i++) {
			b[i] = T.combi(n - 1, i);
		}
		T.DFS(0, 0);
		kb.close();
	}
}

---

코드 설명

조합 계수 생성

b[i] = combi(n - 1, i);

• 맨 윗줄의 각 숫자에 곱할 파스칼 삼각형의 이항계수

---

DFS 탐색

DFS(L + 1, sum + p[L] * b[L]);

• 순열을 완성하며 현재까지의 누적합을 계산
• 마지막 줄 합이 f와 같으면 정답

---

사전순 조건 처리

if (flag) return;

• 조건을 만족하는 수열을 하나 찾으면 이후 탐색 중단
• 처음 찾은 게 사전순 가장 앞선 순열

---

시간 복잡도 분석

• DFS 순열 생성은 O(N!)
• 하지만 조기 종료 조건(flag) 덕분에 사전순 첫 정답에서 바로 종료된다.
• 조합 계산은 O(N²) → 메모이제이션으로 최적화

---

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

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

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