[백준 1988] 낮잠 시간 - JAVA

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

 

dp문제

 

처음에 누적합이 떠올랐는데

조합으로 원소 뽑으려면 3000!/(3000-n)! * n!이여서 불가능했다. 이후 문제분류 보고 풀음

 

 

처음엔 dp[N+1][B+1][2][2]  = dp[N][B][잠 or 안잠][ 준비 or 준비아님]로 생각했다가

경우의 수를 구체화 하다보니 더 간결하게 만들 수 있었고,

 

다음과 같은 식을 세우고 풀었다.

// 1. 잠을 잔 경우
s[n][b] = Math.max(ns[n-1][b-1], s[n-1][b-1] + cost[n]);

// 1-1. 안잤었음, 잠횟수 소모, 안잤었으니 준비 시간임
ns[n-1][b-1]

// 1-2. 잤었음, 잠횟수 소모, 잤었으니 준비 시간 아님
s[n-1][b-1] + cost[n]


// 2. 잠을 안잔 경우
ns[n][b] = Math.max(s[n-1][b], ns[n-1][b]);

// 2-1. 잤었음, 잠횟수 미소모
s[n-1][b]

// 2-2. 안잤었음, 잠횟수 미소모
ns[n-1][b]

 

추가로, 잤을 때 0만큼 피로가 회복되는 경우가 존재하기에 구분하려고 -1로 채웠음

 

 

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    int B = Integer.parseInt(st.nextToken());

    int[] c = new int[N + 1];
    for (int i = 1; i <= N; i++) {
      c[i] = Integer.parseInt(br.readLine());
    }

    // N: n번째 까지 고려 B: 잔 횟수
    // s: 잔 경우 ns: 안잔 경우
    int[][] s = new int[N + 1][B + 1];
    int[][] ns = new int[N + 1][B + 1];
    for (int i = 0; i <= N; i++) {
      Arrays.fill(s[i], -1);
      Arrays.fill(ns[i], -1);
    }

    s[0][1] = 0;
    ns[0][0] = 0;

    for (int n = 1; n <= N; n++) {
      for (int b = 0; b <= B; b++) {

        // 자려면 d를 1 올려야 함
        if (b > 0) {
          int p1 = ns[n - 1][b - 1];
          int p2 = s[n - 1][b - 1];

          if (p1 != -1) {
            s[n][b] = p1;
          }

          if (p2 != -1) {
            s[n][b] = Math.max(s[n][b], p2 + c[n]);
          }
        }

        // 안 자려면 d를 유지 해야 함
        int p3 = s[n - 1][b];
        int p4 = ns[n - 1][b];

        if (p3 != -1) {
          ns[n][b] = p3;
        }

        if (p4 != -1) {
          ns[n][b] = Math.max(ns[n][b], p4);
        }
      }
    }

    int ans = 0;
    for (int e : s[N]) {
      ans = Math.max(ans, e);
    }
    for (int e : ns[N]) {
      ans = Math.max(ans, e);
    }

    System.out.println(ans);
  }
}