최대점수 구하기 ( DFS )

Point : 

생각보다 아래의 if 조건을 떠올리는 것이 빠르게 되지 않는다.

=> 경우의 수는 level이 모든 요소를 완전히 순회했을 때 결정. 

=> 값을 초과하는 경우의 하위 노드는 계산하지 않는다.

if( totalTime > m ) return;

if( level == n ) {
max = Math.max(totalScore, max);
return;
}

 

class Main {

	static int m, n, max;			


	
	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		m = in.nextInt();		
		int [] score;
		int [] time;
		score = new int[n];
		time = new int[n];
		
		for ( int i = 0 ; i < n ; ++i) {
			score[i] = in.nextInt();
			time[i] = in.nextInt();
		}

		M.DFS(0, 0, 0, score, time);
		System.out.println(max);
	}



	private void DFS(int level, int totalScore, int totalTime, int[] score, int[] time) {
		
		if( totalTime > m ) return;
		
		if( level == n ) {
			max = Math.max(totalScore, max);
			return;
		} else {
			DFS( level + 1, totalScore + score[level],
					totalTime + time[level], score, time);
			DFS( level + 1, totalScore,
					totalTime, score, time);
		}
	}
}

ex)
input
5 20
10 5
25 12
15 8
6 3
7 4
output
41