[백준 - 25963] 계단 만들기 (Small) - Java

문제 링크

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

문제

티어: 골드 1
알고리즘: dp

입력

첫 번째 줄에 정수 $N$이 주어진다. $N$은 마인크래프트 맵의 너비이다. ($1 \le N \le 100$)

두 번째 줄에는 $N$개의 수가 주어진다. $i$ 번째 수 $h_i$는 $(i - 1)$ 좌표에 놓인 블록의 높이이다. ($1 \le h_i \le 100$)

블록의 총 개수는 $N\cdot(N + 1) / 2$를 넘지 않는다.

출력

첫 번째 줄에 옮겨야 하는 블록의 최소 수를 한 개의 정수로 출력하시오.

풀이

왼쪽 끝에서 오른 끝으로 안전하게 도달하기 위해 블록을 옮길 때, 옮겨야 하는 블록의 최소 개수를 구해야 한다.

각 열은 가능한 높이가 최대 100이다.

그런데 현재 열이 어떤 높이를 가졌는지에 따라서 블록을 받아와야할 수 있고, 그렇지 않을 수 있다.

• 받아와야하는 경우는 어디서 받아와야할까?
• 블록을 다른 열에 줘야 하는 경우는 어떤 열에 블록을 줘야 할까?

이런 의문이 든다.

단순히 모든 열에 주거나, 모든 열에서 받는 브루트 포스 방식은 불가능하다.

그러면 현재 열에서 받거나 주는 값을 상태로 표시하면 되지 않을까? 라는 생각을 할 수 있다.

예를 들어 첫 번째 열이 5인 상태에서 7 높이를 가지고 싶다면 2개를 다른 열에서 가져와야 한다. 이를 dp의 상태로서 나타내는 것이다.

가져오는 경우는 +로, 주는 경우를 -로 표현한다고 했을 때
-를 표현하기 위해서 N x (N + 1)를 중심으로 잡는다. 왜냐하면 총 블록의 개수가 N x (N + 1)/2이기 때문에 N이 4일 때 총 개수는 10개이며, 10을 중심으로 잡는다면, -10 ~ 0 ~ 10을
0 ~ 10 ~ 20으로 표현할 수 있다.

그리고, 각 열과 높이도 표현해야 되기 때문에 dp는 다음과 같이 정의할 수 있다.
dp[N][H][(N x (N + 1)) x 2]

전체 N이 4일 때
dp[2][4][5]의 의미는 2열에 블록의 높이가 4면서, (10 - 5) => 5개를 다른 열에 줄 수 있는 상태이며, 이 상태에서 최솟값을 의미한다.

반대로 dp[2][4][15]의 의미는 2열에 블록의 높이가 4면서, (10 - 15) => -5, 5개를 다른 열에서 받아와야하는 상태이며, 이 상태에서 최솟값을 의미한다.

그리고 각 상태에서 ex) dp[2][4][5]를 구할 때는 규칙을 만족해야 하기 때문에 dp[1][3][?], dp[1][4][?], dp[1][5][?]중에 최솟값을 넣어주면 된다. (?는 현재 열의 높이에 따라서 다름. 예를 들어 2 번째 열의 높이가 3이라 했을 때 다른 열에서 받아와야할 블록은 총 1개이며 ?는 4가 된다. 왜냐하면 4에서 하나를 가져온다면, +1이 되어서 5가 되기 때문이다. dp[2][4][5]를 구한다 했을 때)

만약 받아온다면, 이미 옮긴 횟수가 포함되었기 때문에 증가시킬 필요가 없고, 다른 열에 준다고 했을 때는 옮긴 횟수를 값에 포함해야 된다.

이런 방식으로 앞에 열부터 가능한 모든 상태를 채운 뒤 마지막에 dp[N][1 ~ 100][N x (N + 1)] 중 최솟값을 출력하면 된다. [N x (N + 1)]인 이유는 이 값이 0 ~ 10 ~ 20에서 10이고, 이 10은 0을 의미하기 때문이다.

이 풀이가 가능한 이유는 규칙을 만족하는 가능한 모든 상태로 다음 상태를 구하기 때문이다.

이 풀이의 시간 복잡도는 O(N x H x N x (N + 1))이다.

소스 코드

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

public class Main {
    static int N;
    static final int initV = Integer.MAX_VALUE;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      int[] map = new int[N + 1];
      StringTokenizer st = new StringTokenizer(br.readLine());
      for(int i=1; i<=N; i++) {
          map[i] = Integer.parseInt(st.nextToken());
      }
      int std = (N * (N + 1)) / 2; //중간 값 100이면 5050 -> 5050은 0을 뜻함.
      int[][][] dp = new int[N + 1][101][(std * 2) + 1];
      init(dp); //initV로 초기값을 채운다.
      
      for(int h=0; h<=100; h++) {
          int needBlocks = h - map[1]; // -는 줄 수 있는거, +는 받아야 하는거, 옮기는 횟수
          if(0 <= (std + needBlocks) && (std + needBlocks) <= std * 2) {
              if(needBlocks >= 0) {
                  dp[1][h][std+needBlocks] = 0;
              } else {
                  //옮겨야 됨
                  dp[1][h][std+needBlocks] = Math.abs(needBlocks);
              }
          }
      }
      
      for(int i=2; i<=N; i++) {
          //열 번호
          for(int h=0; h<=100; h++) {
              //높이
              for(int j=0; j<=std*2; j++) {
                  //dp[2][5][7],
                  //일단 가져와야될 것
                  int needBlocks = h - map[i]; //이 값이 +면 받아야 됨
                  
                  for(int bh=h - 1; bh<=h + 1; bh++) {
                      if(bh < 0) {
                          continue;
                      }
                      
                      if(bh > 100) {
                          break;
                      }
                      
                      if(needBlocks >= 0) {
                          //받아야 하는 값임 +이기 때문에
                          int nextNB = j - needBlocks;
                          if(nextNB >= 0) {
                              //0보다 작으면 모든 블록을 다 빌렸음을 의미한다.
                              if(dp[i - 1][bh][nextNB] != initV) {
                                  dp[i][h][j] = Math.min(dp[i][h][j], dp[i - 1][bh][nextNB]);
                              }
                          }
                      } else if(needBlocks < 0) {
                          //줄 수 있는 경우임.
                          int nextNB = j - needBlocks;
                          if(nextNB <= std * 2) {
                              if(dp[i - 1][bh][nextNB] != initV) {
                                  dp[i][h][j] = Math.min(dp[i][h][j], dp[i - 1][bh][nextNB] + Math.abs(needBlocks));
                              }
                          }
                      } 
                  }
              }
          }
      }
      
      int answer = initV;
      for(int h=0; h<=100; h++) {
          answer = Math.min(answer, dp[N][h][std]);
      }
      System.out.println(answer);
  }
  
  static void init(int[][][] dp) {
      for(int i=0; i<dp.length; i++) {
          for(int j=0; j<dp[i].length; j++) {
              for(int k=0; k<dp[i][j].length; k++) {
                  dp[i][j][k] = initV;
              }
          }
      }
  }
}