인프런 8-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

---

[문제 해결 과정]

이것도 부분집합 문제 풀때랑 마찬가지로 모든 조합을 다 따져봐야한다.
점수가 높아야한다고 해서 뭐 점수 기준으로 내림차순 정렬하고
시간을 비교하기에는 점수 제일 높은 문제를 푼다고 해서 무조건
이득이 아닐 수도 있다.(푸는데 시간 오래 걸릴수도 있으니까)

아무튼 두번째 줄부터 주어지는 점수와 시간을 2차원 배열에 넣는다.
그리고 앞 원소부터 하나씩 내가 풀 문제에 넣을지 말지를 결정하며
가능한 모든 경우의 수를 구한다. 문제 갯수가 N개면 2^N만큼의
경우가 생기겠지만 도중에 제한시간을 넘어버리면 더이상 문제를
풀지 않도록 하면 된다.
그럼 앞 두문제와 동일하게 DFS로 풀면 된다.

1. 문제의 갯수 Num과 제한 시간 Limit을 입력받는다.
2. 그럼 int[N][2] 이차원 배열을 만든뒤
밑줄부터 주어지는 점수와 푸는시간을 저장한다.
3. 첫번째 문제부터 DFS를 시작한다. 넘겨주는 매개변수로는
문제 인덱스(depth)와 문제 푸는데 걸린 총시간(totalTime)이다.
4. 계산하다가 totalTime이 M을 넘어버리면 더이상 DFS 계산하기를 멈춘다.
5. 문제가 총 N개 나오므로 각각의 문제마다 얘를 넣을지 말지 계산해서
어쨌든 depth가 N이 되버리면 이제 판단을 해야한다.
6. totalTime이 M을 안 넘은 애 중에서 점수 최고로 많이 얻은애를 고른다.
7. 걔를 변수에 넣어놓고 점수 높은거 나올때마다 그걸로 덮어쓴다.

[통과한 코드]

import java.util.Scanner;

public class Main {
	static int maxScore = 0;
	static int Num = 0;
	static int Limit = 0;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
	    Num = sc.nextInt(); // 문제 갯수
	    Limit = sc.nextInt(); // 제한 시간
	    int sum = 0;
	    
	    int[][] question = new int[Num][2];
	    
	    for(int i = 0 ; i < Num ; i++) {
	    	question[i][0] = sc.nextInt();
	    	question[i][1] = sc.nextInt();
	    	// 점수와 푸는데 걸리는 시간 넣어주기
	    }
	    
	    DFS(0, 0, 0, question);
	    
    	System.out.println(maxScore);
	}

	private static void DFS(int depth, int totalScore, int totalTime, int[][] question) {
		if(totalTime > Limit) {
			return;
			// 문제 푼 시간이 제한 시간 넘어가면 그대로 DFS 끝
		}
		
		if(depth == Num) {
			if(totalTime <= Limit && totalScore > maxScore) {
				maxScore = totalScore;
				// 방금 푼 문제수가 많다면 걔로 값 교체
			}
		} else {
			DFS(depth+1, totalScore+question[depth][0], totalTime + question[depth][1], question);
			// 문제 푼 경우. 그럼 그 시간만큼 더해주기
			DFS(depth+1, totalScore, totalTime, question);
			// 문제 안 품. 그럼 시간 안 더해지고 깊이만 깊어짐.
		}
	}
}

 

[후기]

계속 DFS 문제만 푸니까 확실히 이 유형은 어떻게 풀어야되는지 알 것 같긴 하다. 이렇게 유형 하나씩 조져야겠다!