[백준 - 30016번] 공부 계획하기 - Java

문제 링크

https://www.acmicpc.net/problem/30016

문제

티어: 골드 1
알고리즘: dp
무대소녀 바나나는 고등학교 3학년이 되었다. 명문 대학을 가고 싶은 그녀이지만, 평소 연기 연습만을 하며 내신 공부를 전혀 하지 않았던 바나나는 정신을 차리고 $T$시간 뒤에 있는 수능을 위해 공부하기로 마음먹었다. 그러나 공부 경험이 없는 바나나는 공부를 얼마나 해야 하는지를 알 수 없었다. 바나나를 위해 공부 스케줄을 짜주자!

수능에는 $N$개의 과목이 있다. $i$ $(1\leq i\leq N)$번 과목을 총 $j$ $(0\leq j\leq T)$시간 공부했을 때 받을 수 있는 점수를 $S_{i,j}$ 라 하자. 바나나가 지켜오던 스케줄에 따라, 각 과목의 공부 시간은 음이 아닌 정수여야 함에 주의하자.

그러나 인간의 체력에 한계가 있기 때문에 하루 종일 공부를 하는 것은 힘들다. 총 $X$ $(0\leq X\leq T)$시간 만큼 공부를 하면 피곤해져서 총 점수가 $D_{X}$만큼 감소하게 된다. 이로 인하여 점수가 음수가 될 수도 있음에 주의하자.

당신은 최적의 방법으로 공부를 하였을 때 바나나가 얻을 수 있는 최대 점수와 그때의 공부 방법을 구해야 한다.

입력

첫째 줄에는 수능 과목의 수 $N$과 $T$가 공백으로 구분되어 주어진다.

둘째 줄부터 $N+1$번째 줄까지는 $i+1$ $(1\leq i\leq N)$번째 줄에 $i$번째 과목을 $j$ $(0\leq j\leq T)$시간 공부했을 때 받을 수 있는 점수에 대한 $T+1$개의 수 $S_{i,0}$, $S_{i,1}$, $\cdots$, $S_{i,T}$가 공백으로 구분되어 주어진다.

$N+2$번째 줄에는 $T+1$개의 수 $D_{0}$, $D_{1}$, $\cdots$, $D_{T}$가 공백으로 구분되어 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

첫째 줄에 바나나가 받을 수 있는 최대 점수
$score$를 출력하라.

둘째 줄에 각 과목 별로 공부해야 하는 시간을 뜻하는
$N$개의 정수 $A_{1}$, $A_{2}$, $\cdots$, $A_{N}$을 공백으로 구분하여 출력하라. 만약 최대 점수를 받는 공부 방법이 여러 가지라면, 그 중 아무거나 출력해도 좋다.

제한

풀이

바나나가 받을 수 있는 최대 점수 score를 출력해야 한다.

과목마다 공부할 시간을 정한다고 생각하면 쉽게 풀 수 있다.

첫 번째 과목에서 1 ~ T시간
두 번째 과목에서 1 ~ T시간

각 과목에서 1 ~ T시간 공부한다고 했을 때 구하고자 하는 총 시간에서 현재 과목에서 공부한 시간을 뺀 leftTime으로 전 과목까지 공부했을 때 최댓값 + 현재 과목에서 얻은 점수을 해주면 된다. 그러면 이런 식으로 1 ~ T 시간을 공부하면 현재 상태에 최댓값을 유지할 수 있다.

이를 토대로 dp를 정의하면 dp[N][T]가 되며
dp[3][4]를 구한다고 했을 때 3과목까지 공부한 총 시간은 4시간일 때 최댓값을 의미한다.

dp[3][4]를 구하는 과정은 1 ~ 4까지 현재 과목에서 공부할 시간을 정해준다.
만약 1시간을 공부한다면 남은 시간 3시간이기 때문에 dp[2][3] + (현재 과목에서 1시간 공부했을 때 값)이 된다. 그래서 그 중 가장 큰 값을 d[3][4]에 넣어준다면, 다음번 dp[3][4]가 사용될 때 이 값이 최댓값이기 때문에 이후에도 최댓값을 유지해 줄 수 있는 것이다.

마지막으로 바나나가 받을 수 있는 최대 점수를 구해야 하기 때문에 dp에 각 상태를 돌며, 총 공부한 시간(X)을 가지고 D를 구해서 빼주면 얻을 수 있는 점수가 되며, 그 점수가 최대 점수인 값이 답이 된다.

그리고 각 과목을 공부한 시간을 출력해야 되기 때문에 이는 dp 각 상태마다 String 문자열을 유지하며 현재 과목에서 공부한 시간을 붙여나가면 최댓값일 때 공부 방법을 알 수 있다.

이 풀이의 시간 복잡도는 O(100^3)이다.

소스 코드

import java.io.*;
import java.util.*;

class State {
    int S;
    String time;
    State(int S, String time) {
        this.S = S;
        this.time = time;
    }
}

public class Main {
    static int N,T;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      N = Integer.parseInt(st.nextToken());
      T = Integer.parseInt(st.nextToken());
      int[][] subjects = new int[N + 1][T + 1];
      for(int i=1; i<=N; i++) {
          StringTokenizer st2 = new StringTokenizer(br.readLine());
          for(int j=0; j<=T; j++) {
              subjects[i][j] = Integer.parseInt(st2.nextToken());
          }
      }
      int[] D = new int[T + 1];
      StringTokenizer st2 = new StringTokenizer(br.readLine());
      for(int i=0; i<=T; i++) {
          D[i] = Integer.parseInt(st2.nextToken());
      }
      State[][] dp = new State[N + 1][T + 1];
      for(int i=0; i<=T; i++) {
          dp[1][i] = new State(subjects[1][i], String.valueOf(i));
      }
      
      for(int i=2; i<=N; i++) {
          for(int j=0; j<=T; j++) {
              for(int k=0; k<=j; k++) {
                  int leftT = j - k; //현재 과목을 공부하고 남은 시간
                  int newS = (dp[i - 1][leftT].S + subjects[i][k]);
                  if(dp[i][j] == null || dp[i][j].S < newS) {
                      //newS가 더 크다면
                      dp[i][j] = new State(newS, dp[i -1][leftT].time + " " + k);
                  }
              }
          }
      }
      
      State answer = new State(0 - D[0], " ");
      for(int i=1; i<=N; i++) {
          for(int j=1; j<=T; j++) {
              int score = dp[i][j].S - D[j];
              if(answer.S < score) {
                  answer = new State(score, dp[i][j].time);
              }
          }
      }
      StringBuilder sb = new StringBuilder();
      sb.append(answer.S).append("\n");
      
      String[] split = answer.time.split(" ");
      for(int i=0; i<N; i++) {
          if(i < split.length) {
              sb.append(split[i]).append(" ");
          } else {
              sb.append(0).append(" ");
          }
      }
      System.out.println(sb.toString().trim());
  }
}