최대점수 구하기(DFS)

설명

 

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 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 를 이용해 해결할 수 있다.

 

static int N, M;
static int[] problemNum, TimeLimit;
static int maxScore;

 

먼저 문제의 수 N과, 제한 시간 M, 문제 개수, 최대 점수 maxScore를 전역변수로 입력받고 문제 개수 problemNum과 시간 제한을 나타내는 TimeLimit을 배열로 선언한다.

 

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    N = in.nextInt();
    M = in.nextInt();

    problemNum = new int[N];
    TimeLimit = new int[N];

    for (int i = 0; i < N; i++) {
        problemNum[i] = in.nextInt();
        TimeLimit[i] = in.nextInt();
    }

    DFS (0,0,0);
    System.out.println(maxScore);

}

 

problemNum과 TimeLimit 배열을 크기 N으로 초기화해주고 문제의 개수(N)만큼 for문을 돌며 문제의 개수 배열, 제한시간 배열 각각의 배열에 입력 받아준다.

그 이후 DFS 함수를 호출하고 maxScore를 출력한다.

 

//문제를 풀지 안 풀지
public static void DFS(int L, int sumScore, int sumTime) {
    if(sumTime > M) return; //M을 넘으면 return

    if(L == N) { //모든 문제를 고ㅕ려했을 때
        if(sumScore > maxScore)
            maxScore = sumScore; //maxScore 갱신
    } else {
        DFS(L + 1, sumScore + problemNum[L], sumTime + TimeLimit[L]); //문제 풀 때
        DFS(L + 1, sumScore, sumTime); //문제 안 풀 때
    }
}

 

DFS 함수이다. 레벨 L, 레벨을 탐색해가며 점수를 더할 sumScore변수, 제한 시간을 더해갈 sumTime을 받아준다.

• 만약 sumTime이 제한시간 M을 넘으면 return한다.
• 만약 L==M 즉 모든 문제를 탐색 완료했으면, 이때 sumScore가 maxScore보다 크다면 maxScore를 갱신해준다.
• 그리고 아직 모든 문제를 탐색하지 못 했다면 문제를 풀지 안 풀지 두 가지로 나누어 탐색할 수 있다.
  • 문제 풀 때 DFS(L + 1, sumScore + problemNum[L], sumTime + TimeLimit[L])
    • 현재 점수에 해당 문제의 점수를 더하고, 현재의 시간에 해당 문제의 시간을 추가한 후 다음 레벨로 넘어간다.
  • 문제 안 풀 때 DFS(L + 1, sumScore, sumTime)
    • 점수는 그대로 유지하고 다음 레벨로 넘어간다.

 

최종 코드

 

import java.util.Scanner;

public class P03_최대점수구하기 {
    static int N, M;
    static int[] problemNum, TimeLimit;
    static int maxScore;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();

        problemNum = new int[N];
        TimeLimit = new int[N];

        for (int i = 0; i < N; i++) {
            problemNum[i] = in.nextInt();
            TimeLimit[i] = in.nextInt();
        }

        DFS (0,0,0);
        System.out.println(maxScore);

    }

    //문제를 풀지 안 풀지
    public static void DFS(int L, int sumScore, int sumTime) {
        if(sumTime > M) return; //M을 넘으면 return

        if(L == N) { //모든 문제를 고ㅕ려했을 때
            if(sumScore > maxScore)
                maxScore = sumScore; //maxScore 갱신
        } else {
            DFS(L + 1, sumScore + problemNum[L], sumTime + TimeLimit[L]); //문제 풀 때
            DFS(L + 1, sumScore, sumTime); //문제 안 풀 때
        }
    }
}