Java : 최대 점수 구하기 (DFS)

풀이

• Node 클래스에 score, times 변수를 만들고 노드 마다 아래 조건을 비교하면서 최대 점수를 갱신하였다.
  1. m 시간을 넘기면 return한다.
  2. 최대 점수와 비교했을 때 현재 점수가 더 크면 새로 갱신한다.
  3. 배열의 수 보다 깊이가 깊어지면 바로 return

구현

package inflearn;

import java.util.Scanner;

public class I0803 {
	static Node[] arr;
	static int m;
	static int sum = 0;
	static int maxScore = 0;
	static int maxTimes = 0;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		m = sc.nextInt();
		arr = new Node[n + 1];
		arr[0] = new Node(0, 0);
		for (int i = 1; i <= n; i++) {
			int score = sc.nextInt();
			int times = sc.nextInt();

			arr[i] = new Node(score, times);
		}
		int l = 0;
		int t = 0;
		dfs(l, arr[0].getScore(), arr[0].getTimes());
		System.out.println(maxScore);
	}

	static void dfs(int level, int score, int times) {

		if (m >= times) {
			if (score > maxScore) maxScore = score;
			maxTimes = times;
		} else return;
		if (level == arr.length - 1) return;
		dfs(level + 1, score + arr[level + 1].getScore(), times + arr[level + 1].getTimes());
		dfs(level + 1, score, times);
	}
}

class Node {
	private final int score;
	private final int times;

	public Node(int size, int val) {
		this.score = size;
		this.times = val;
	}

	public int getTimes() {
		return this.times;
	}

	public int getScore() {
		return this.score;
	}
}