[DFS] 최대점수 구하기 .java

설명

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

 

 

내 풀이

•  점수 배열과 시간 배열은 인덱스가 동일하기 때문에 따로 입력 받음
• 점수의 합 변수 sum, 시간의 합 변수 t 를 두어 t > c 일때 재귀 종료로 설정
• 모든 문제를 다 탐색했을 때의 합을 정답 변수에 최댓값으로 갱신

import java.util.Arrays;
import java.util.Scanner;


public class Main {

    static int n, m;
    static int answer =Integer.MIN_VALUE;

    public static void dfs(int L, int sum,int t, int[] score,int[] time) {
        if(t > m) return;//시간초과
        if(L == n) {
            answer = Math.max(answer, sum);
        } else {
            dfs(L+1,sum+score[L], t+time[L],score,time);
            dfs(L+1,sum,t,score,time);
        }


    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        int[] score = new int[n];
        int[] time = new int[n];
        for(int i = 0; i <n; i++) {
            score[i] = sc.nextInt();
            time[i] = sc.nextInt();
        }

        dfs(0,0,0,score,time);
        System.out.print(answer);

    }

}

 

 

다른 풀이

변수명만 다르고 동일

import java.util.Scanner;


public class Main {

    static int n, m;
    static int answer =Integer.MIN_VALUE;

    public static void dfs(int L, int sum,int time, int[] ps,int[] pt) {
        if(time > m) return;//시간초과
        if(L == n) {
            answer = Math.max(answer, sum);
        } else {
            dfs(L+1,sum+ps[L], time+pt[L],ps,pt);
            dfs(L+1,sum,time,ps,pt);
        }


    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        int[] a = new int[n];//점수
        int[] b = new int[n];//시간
        for(int i = 0; i <n; i++) {
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
        }

        dfs(0,0,0,a,b);
        System.out.print(answer);

    }

}