[인프런] 08_03 동전교환(DFS)

📖  문제

---

• 첫 번째 줄에 문제의 개수N(1<=N<=20)과 제한 시간 M(10<=M<=300)이 주어집니다.
• 두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.
  • 이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다.제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다.
  • 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다.

출력 예시

 

⚠️  주의사항

---

• 중복 풀이 불가능

 

✍️  이해

---

/**
 * 1. 주어진 입력들 입력 -> 점수와 시간은 각각 1차원 배열로 입력
 * 2. 푼 문제들의 합이 주어진 시간보다 크면 return
 * 3. 끝까지 돌았을 경우 현재 갖고 있는 값보다 문제 푼 점수가 높으면 값 대입
 * 4. 풀었을 경우, 못풀었을 경우 2가지의 경우의 수 반복
 */

 

✏️  풀이

---

import java.util.Scanner;

public class Main {

    static int N, M, answer;

    public void DFS(int L, int sum, int time, int[] A, int[] B) {
        if (time > M) return;

        if(L == N){
            answer = Math.max(answer, sum);
        }else{
            DFS(L + 1, sum + A[L], time + B[L], A, B);
            DFS(L + 1, sum, time , A, B);
        }
    }

    public static void main(String[] args) {
        Main T = new Main();

        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(); // 시간
        }

        T.DFS(0, 0, 0, A, B);

        System.out.println(answer);
    }

---