fragment-header
fragment-markdown
홈
로그인
로그아웃
내 블로그
설정
로그인
백준 25963 (C++) 계단 만들기 (Small)
최초 업로드: 2025-11-19 13:37:04
최근 수정 시간: 2025-11-19 13:39:59
게시자: rlatjwls3333
카테고리: 백준
조회수: 7
# [Gold I] 계단 만들기 (Small) [문제 링크](https://www.acmicpc.net/problem/25963) ## 문제 설명 <p>때는 2013년, 잼민이 지수는 마인크래프트 게임을 열심히 하고 있다.</p> <p>지수가 하는 마인크래프트에서는 점프는 한 칸밖에 되지 않으며, 신기하게도 두 칸 이상부터 즉사 낙하 데미지가 들어간다! 따라서 한 곳에서 다른 한 곳으로 이동하기 위해서는 인접한 열의 높이 차가 $1$ 이하여야만 한다. 또한, 모든 블록은 공중에 떠 있을 수 없다.</p> <p style="text-align: center;"><img alt="" src="https://upload.acmicpc.net/886e9077-a576-4fdd-a5b9-4a05f9756981/-/preview/" style="width: 247px; height: 345px;"></p> <p>위 그림에서처럼 지수는 왼쪽 끝에서 오른쪽 끝으로 이동하고자 한다. 그런데 지금 상태에서는 인접한 열의 높이 차가 $2$ 이상인 곳이 있어 지수의 캐릭터가 즉사하게 된다. 따라서 몇 개의 블록을 옮겨 블록의 높이 차가 최대 $1$이 되게 하고자 한다. 그러나 지수는 매우 게으른 성격이기 때문에 최소한의 블록만 옮기고 싶다.</p> <p style="text-align: center;"><img alt="" src="https://upload.acmicpc.net/0d57b1f9-8864-42e8-a38e-37d7208bea2c/-/preview/" style="width: 247px; height: 345px;"></p> <p>위 예시에서는 두 개의 블록을 옮기면 모든 인접한 블록의 높이 차가 최대 $1$이 된다!</p> <p>지수가 왼쪽 끝에서 오른쪽 끝으로 안전하게 도달하기 위해 블록을 옮길 때, 옮겨야 하는 블록의 최소 개수를 구하시오.</p> ## 입력 <p>첫 번째 줄에 정수 $N$이 주어진다. $N$은 마인크래프트 맵의 너비이다. ($1 \le N \le 100$)</p> <p>두 번째 줄에는 $N$개의 수가 주어진다. $i$ 번째 수 $h_i$는 $(i - 1)$ 좌표에 놓인 블록의 높이이다. ($1 \le h_i \le 100$)</p> <p>블록의 총 개수는 $N\cdot(N + 1) / 2$를 넘지 않는다.</p> ## 출력 <p>첫 번째 줄에 옮겨야 하는 블록의 최소 수를 한 개의 정수로 출력하시오.</p> ## 풀이 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; } ```