섹션 8 DFS, BFS - 3. 최대점수 구하기(DFS)

📌 문제 설명

정보올림피아드 대회 준비를 위해 현수는 선생님이 준 N개의 문제 중에서 최대한 많은 점수를 얻고자 한다.
각 문제는 정해진 점수와 소요 시간이 있으며 총 제한 시간 M분 안에 풀 수 있는 문제들을 선택해
얻을 수 있는 최대 점수를 구하라.

• 각 문제는 한 번만 풀 수 있다.
• 선택한 문제들의 총 소요 시간이 M을 넘으면 안 된다.

---

📝 입력 & 출력

입력

• 첫 줄: 문제 개수 N (1 ≤ N ≤ 20), 제한 시간 M (10 ≤ M ≤ 300)
• 다음 N줄: 각 문제의 점수, 소요 시간

출력

• 제한 시간 안에 얻을 수 있는 최대 점수

---

🔹 예제 입력 & 출력

예제 입력

 

5 20
10 5
25 12
15 8
6 3
7 4

예제 출력

 

41

💬 설명

• 25점(12분) + 6점(3분) + 10점(5분) → 총 43점, 20분
• 하지만 이렇게 선택하면 43점이지만 20분이 초과됨
• 가장 좋은 선택은 25점(12분) + 6점(3분) + 10점(5분) → 정확히 20분 → 41점

---

💡 해결 방법

✅ 접근 전략 (DFS + 백트래킹)

• 모든 문제에 대해 풀거나 / 안 푸는 두 가지 선택지로 DFS를 탐색
• 현재까지의 누적 시간 time이 제한시간 M을 초과하면 가지치기
• 끝까지 탐색한 경우(L == N)엔 현재 점수 합을 최대값과 비교하여 갱신

---

💻 코드 구현 (Java)

package partDfsBfs;

import java.util.*;

public class Problem3 {
	static int N, M;
	static int answer = 0;

	public void DFS(int L, int sum, int time, int[] ps, int[] pt) {
		if (time > M) return; // ❗ 가지치기: 제한시간 초과 시 중단
		if (L == N) {
			answer = Math.max(answer, sum);
		} else {
			DFS(L + 1, sum + ps[L], time + pt[L], ps, pt); // 문제를 푼다
			DFS(L + 1, sum, time, ps, pt);                 // 문제를 안 푼다
		}
	}

	public static void main(String[] args) {
		Problem3 T = new Problem3();
		Scanner kb = new Scanner(System.in);
		N = kb.nextInt();
		M = kb.nextInt();
		int[] score = new int[N];
		int[] time = new int[N];
		for (int i = 0; i < N; i++) {
			score[i] = kb.nextInt();
			time[i] = kb.nextInt();
		}
		T.DFS(0, 0, 0, score, time);
		System.out.println(answer);
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 입력 처리 및 초기화

int[] score = new int[N];
int[] time = new int[N];
for (int i = 0; i < N; i++) {
	score[i] = kb.nextInt();
	time[i] = kb.nextInt();
}

• 점수 배열과 소요 시간 배열로 분리 저장

---

2️⃣ DFS 함수 정의

public void DFS(int L, int sum, int time, int[] ps, int[] pt)

• L: 현재 문제 인덱스
• sum: 누적 점수
• time: 누적 소요 시간

---

3️⃣ 가지치기 & 종료 조건

if (time > M) return;         // 시간 초과 시 탐색 중단
if (L == N) answer = Math.max(answer, sum); // 끝까지 탐색하면 최대 점수 갱신

---

4️⃣ 포함 / 미포함 분기

DFS(L + 1, sum + ps[L], time + pt[L], ps, pt); // 푼다
DFS(L + 1, sum, time, ps, pt);                 // 안 푼다

• 각 문제를 풀지 않는 경로도 반드시 확인해야 한다

---

⏳ 시간 복잡도 분석

• 문제 수 N에 대해 2^N 개의 조합 → 최대 2^20 ≈ 100만
• 각 경로마다 O(1) 연산이므로 완전 탐색 가능
• 가지치기(time > M) 덕분에 탐색 시간이 더 줄어듦

---

🧠 핵심 정리

• 제한 조건을 만족하는 최댓값을 찾는 문제는 대부분 DFS + 백트래킹
• 누적된 시간이나 비용이 제한을 넘을 경우 가지치기 필수
• 모든 조합을 완전 탐색하되 조건 충족 여부를 체크하며 최댓값 갱신

---

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

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

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