자바 알고리즘 문제 풀이 입문. ch08. DFS, BFS 활용 : 최대점수 구하기 DFS

 

 

https://hyejin.tistory.com/1276

자바 알고리즘 문제 풀이 입문. ch08. DFS, BFS 활용 : 바둑이 승차 DFS

-> 이전 문제 풀이 

 

 

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

 

 

문제 풀이 1

public class GetMaximumScore
{
   static int n, m, max;
   static int[] score, times;
   
   public void DFS(int L, int time, int sum)
   {
      if (time > m) {
         return;
      }
      if (L == n) {
         if (sum > max) max = sum;
      }else {
         DFS(L + 1, time + times[L], sum + score[L]);
         DFS(L + 1, time, sum);
      }
   }
   
   public static void main(String[] args)
   {
      GetMaximumScore getMaximumScore = new GetMaximumScore();
      Scanner scanner = new Scanner(System.in);
      n = scanner.nextInt();
      m = scanner.nextInt();
      score = new int[n];
      times = new int[n];
      
      for (int i = 0; i < n; i++)
      {
         score[i] = scanner.nextInt();
         times[i] = scanner.nextInt();
      }
      
      getMaximumScore.DFS(0, 0, 0);
      System.out.println(max);
      
   }
}

👩🏻‍💻 : 이 문제는 합이 같은 부분집합, 바둑이 승차 과 같이 부분 집합 풀이 방식으로 풀어주면 된다. (문제 풀이 방식이 완전 같음) 

대신 이 문제에서는 점수와 시간이 주어진다. 주어진 최대 시간을 넘기지 않으면서 최대 합을 구하면 된다. 

 

따라서 score, time 각각 1차원 배열을 만들어주고, 그 다음에는 비슷하게 문제를 풀면 된다. 

문제를 풀고, 안풀고에 따라서 문제를 푼다고 생각하면 sum에 score[L]을 더하면서 time에 times[L]을 더해주거나, 

문제를 풀지 않을 때는 그냥 sum과 time 값을 넘겨주면 된다. 

 

L이 n까지 갔을 때는 max가 sum보다 작을 경우 sum의 값을 max에 대입해주고 반환하면 된다. 

또는 time이 m보다 커질 경우에는 주어진 시간안에 문제를 풀지 못하는 것이기 때문에 return 해주면 된다. 

 

 

 

문제 풀이 2

public class GetMaximumScore2 {
    static int answer = Integer.MIN_VALUE, n, m;
    boolean flag = false;

    // ps : score, pt : time
    public 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) {
        GetMaximumScore2 getMaximumScore2 = new GetMaximumScore2();
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];

        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
            b[i] = scanner.nextInt();
        }

        getMaximumScore2.DFS(0, 0, 0, a, b);
        System.out.println(answer);
    }
}

👾 : 강사님도 비슷하게 풀셨는데, 강사님은 DFS 메서드에 매개변수로 점수와 시간 배열도 함께 넘겨주고 있다. 

ps는 점수 배열을 의미하고, pt는 시간 배열을 의미한다. 

 

문제를 풀 때는

DFS(L + 1, sum + ps[L], time + pt[L], ps, pt); // 문제를 풀 때

이 재귀함수를 호출하는 것이고, 

 

문제를 풀지 않을 때는 

DFS(L + 1, sum, time, ps, pt); // 문제를 풀지 않을 때

이 재귀함수를 호출해서 각각의 부분집합을 만들어 나간다. 

 

그리고 time이 제한된 시간 m 을 넘길 수 없으므로 m보다 커지면 return 해줘 함수를 종료하고, 

L이 n까지 단계가 내려갔을 때는 answer 와 sum 값을 비교해서 큰 값을 answer에 담아주면 된다.