[PS] 인프런 강의 - DFS 3. 최대점수 구하기

 

문제

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다.

제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주하고, 한 유형당 한개만 풀 수 있습니다.)

 

▣ 입력설명
첫 번째 줄에 문제의 개수N(1<=N<=20)과 제한 시간 M(10<=M<=300)이 주어집니다.
두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.

 

▣ 출력설명
첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.

 

▣ 입력예제 1
5 20
10 5
25 12
15 8
6 3
7 4

 

▣ 출력예제 1
41

풀이

부분집합 트리 푸는 문제풀이와 같다. 그것에 대한 연습이다.

앞서 푼 바둑이 문제랑 코드가 거~의 같다.

 

이제야 감이 좀 잡히는데 정리해보면 

 

• DFS (깊이우선탐색) : 부분집합, 중복 안되는 것(집합원소, 문제 등)을 선택 할지, 안 할지 경우의 수가 나뉘는 문제
  • 트리예시 : D(0, sum)
    • 0번째 요소를 선택 O → D(1, sum + 요소속성)
    • 0번째 요소를 선택 X → ㅇ(1, sum)
• BFS (넓이우선탐색, 레벨 탐색) : 말단 노드로 가는 가장 짧은경로(=레벨) 구하는 문제, 최소길이. 최소이동 구하기
  • 큐 사용,  요소를 넣어둔 배열을 순회하면서 레벨 별로 큐에 offer 했다가 poll
  • 효율을 위해 중복 순회 체크 (상황에 따라 다름)
    • 트리 예시 : D(1) →   D(0)  D(1)   D(2)  D(3) ..   D(n) 
    •                    D(2) →  D(0)  D(1)   D(2)  D(3) ..   D(n)

 

아무래도 이런 느낌인 듯하다.

 

코드

import java.util.Scanner;

public class Main {
	
	static int answer = Integer.MIN_VALUE; //최대값을 구해야하니까
	static int[] g,t;
	static int n, m;
	
	public static void DFS(int i, int g_sum, int t_sum) {
		if(t_sum > m) return; //20초보다 더 걸리면 돌아가기
		
		//그래프 마지막 정점
		if(i == n) {
			answer = Math.max(answer, g_sum);
		}
		else {
			DFS(i+1, g_sum + g[i], t_sum + t[i]); //푼다
			DFS(i+1, g_sum, t_sum); //안푼다
		}
	}

	public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        n = in.nextInt(); //1~20 문제 개수
        m = in.nextInt();//10~300 제한 시간
        g = new int[n];//점수
        t = new int[n];//시간
        
        for(int i=0; i<n; i++) {
        	g[i] = in.nextInt(); 
        	t[i] = in.nextInt(); 
        }
        
        DFS(0, 0, 0);
        System.out.print(answer);
        
    }
}