[알고리즘]DFS - 최대점수 구하기

문제를 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어질 때, 제한시간 M 안에 얻을 수 있는 최대 점수를 출력하는 프로그램

 

 

import java.util.Scanner;

public class Main {
	static int answer = Integer.MIN_VALUE, n, m; // answer : 최대점수
	
	public static void DFS(int level, int sum, int cnt, int[] score, int[] time) {
		if (cnt>m) return; // 시간제한 초과
		if (level==n) { // 부분집합 완성
			answer = Math.max(answer, sum);
		}
		else {
			DFS(level+1, sum+score[level], cnt+time[level], score, time);
			DFS(level+1, sum, cnt, score, time);
		}
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt(); // 문제 개수
		m = scanner.nextInt(); // 제한 시간
		int[] score = new int[n]; // 점수
		int[] time = new int[n]; // 시간
		for (int i=0; i<n; i++) {
			score[i] = scanner.nextInt();
			time[i] = scanner.nextInt();
		}
		DFS(0, 0, 0, score, time);
		System.out.println(answer);
	}

}

---

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