[인프런 자바/java] 3. 최대점수 구하기(DFS) _디버깅의 눈물

체크 포인트

 

1. DFS(깊이 우선 탐색)을 이용하는 문제

-제한 시간 안에 얻을 수 있는 '최대 점수'를 구하는 문제

-배열에 존재하는 0번째 문제부터

(1)해당 문제를 풀이한 경우와

(2)해당 문제를 풀이하지 않은 경우로 나누어

-'모든 경우의 수를 탐색'한 후, 얻을 수 있는 최대 점수를 구해야 한다.

 

 

2. '문제를 푼 경우'와 '풀지 않은 경우'를 DFS로 표현

 

    		// 해당 문제를 풀이한 경우, 문제풀이 시간 및 총합 점수 증가
    		DFS(L+1, timeSum+map[L][1], sum+map[L][0]);
    		// 해당 문제를 풀이하지 않은 경우,
    		DFS(L+1, timeSum, sum);

 

 

3. 문제 풀이 제한시간에 도달한 경우와 마지막 문제에 도달한 경우의 처리

(1)문제 풀이 제한시간에 도달한 경우,

    	// 문제 풀이 시간이 제한 시간을 넘은 경우,
    	if(timeSum>M) {
    		return;
    	}

 

 

(2)마지막 문제에 도달한 경우,

    	// N번째 문제에 도달한 경우,
    	if(L==N) {
    		return;
    	}

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public  class Main {
	// 문제의 개수 N, 제한 시간 M
	static int N, M;
	// '점수'와 '푸는 시간'을 담아주는 배열
	static int[][] map;
	// 점수 합의 최대값 max
	static int max;
	// 점수의 합
	static int sum;
	// 문제 풀이 시간의 총합
	static int timeSum;
	
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    	
    	// 문제의 개수 N
    	N = Integer.parseInt(st.nextToken());
    	// 제한 시간 M
    	M = Integer.parseInt(st.nextToken());
    	
    	// 배열 초기화
    	map = new int[N][M];
    	
    	// 배열에 값 입력
    	for(int i=0; i<N; i++) {
    		
    		st = new StringTokenizer(br.readLine(), " ");
    		
    		for(int j=0; j<2; j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	/*
    	for(int i=0; i<N; i++) {
    		
    		for(int j=0; j<2; j++) {

    			if(j==1) {
    				System.out.println(map[i][j] + " ");
    			}
    			else {
    				System.out.print(map[i][j] + " ");
    			}
    		}
    	}
    	*/
    	
    	// max 값 초기화
    	max = Integer.MIN_VALUE;
    	
    	// DFS 탐색 시작
    	DFS(0, 0, 0);
    	
    	System.out.println(max);
    	
    }
    
    static void DFS(int L, int timeSum, int sum) {

    	// 문제 풀이 시간이 제한 시간을 넘은 경우,
    	if(timeSum>M) {
    		return;
    	}
    	
    	// 점수의 총합이 기존 점수 총합보다 높은 경우,
    	if(sum>max) {
    		max = sum;
    	}
    	
    	// 문제 탐색의 단계(L)가 총 문제수보다 낮은 경우,
    	// 배열의 0번째, 1번째 ... N-1번째 문제까지 탐색
    	if(L!=N) {
    		// 해당 문제를 풀이한 경우, 문제풀이 시간 및 총합 점수 증가
    		DFS(L+1, timeSum+map[L][1], sum+map[L][0]);
    		// 해당 문제를 풀이하지 않은 경우,
    		DFS(L+1, timeSum, sum);
    	}
    	
    	// N번째 문제에 도달한 경우,
    	if(L==N) {
    		return;
    	}
    }
    

} // end of Main