백준 25963 (C++) 계단 만들기 (Small)

최초 업로드: 2025-11-19 13:37:04

최근 수정 시간: 2025-11-19 13:39:59

게시자: rlatjwls3333

카테고리: 백준

# [Gold I] 계단 만들기 (Small)

[문제 링크](https://www.acmicpc.net/problem/25963)

## 문제 설명

때는 2013년, 잼민이 지수는 마인크래프트 게임을 열심히 하고 있다.

지수가 하는 마인크래프트에서는 점프는 한 칸밖에 되지 않으며, 신기하게도 두 칸 이상부터 즉사 낙하 데미지가 들어간다! 따라서 한 곳에서 다른 한 곳으로 이동하기 위해서는 인접한 열의 높이 차가 $1$ 이하여야만 한다. 또한, 모든 블록은 공중에 떠 있을 수 없다.

위 그림에서처럼 지수는 왼쪽 끝에서 오른쪽 끝으로 이동하고자 한다. 그런데 지금 상태에서는 인접한 열의 높이 차가 $2$ 이상인 곳이 있어 지수의 캐릭터가 즉사하게 된다. 따라서 몇 개의 블록을 옮겨 블록의 높이 차가 최대 $1$이 되게 하고자 한다. 그러나 지수는 매우 게으른 성격이기 때문에 최소한의 블록만 옮기고 싶다.

위 예시에서는 두 개의 블록을 옮기면 모든 인접한 블록의 높이 차가 최대 $1$이 된다!

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

## 입력

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

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

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

## 출력

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

## 풀이
dp[i][j][k]를 i번째 위치를 볼 때, 지금까지의 총 블럭 수가 j개이고, 현재의 블럭 수가 k인 경우의 최소 cost라고 정의를 하면 -1 ~ 1 사이의 l에 대해 abs(a[i]-(k+l)) + dp[i][j-(k+l)][k+l]중 최솟값으로 정해진다.

정답은 dp[n-1][전체 블럭 수][0 ~ 100]의 최솟값이다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
int a[100], dp[100][10001][101];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;

int sum=0;
 for(int i=0;i<n;i++) {
 cin >> a[i];
 sum += a[i];
 }

fill(&dp[0][0][0], &dp[99][10000][101], INF);
 for(int i=1;i<=100;i++) dp[0][i][i] = abs(a[0]-i);
 for(int i=1;i<n;i++) {
 for(int j=1;j<=sum;j++) {
 for(int k=1;k<=100;k++) {
 for(int l=-1;l<=1;l++) {
 if(j-k>=0 && 0<=k+l && k+l<=100) dp[i][j][k] = min(dp[i][j][k], abs(a[i]-k) + dp[i-1][j-k][k+l]);
 }
 }
 }
 }
 cout << *min_element(&dp[n-1][sum][0], &dp[n-1][sum][101])/2;
}
```