[백준/BOJ] 25963 계단 만들기 (Small) - 접근과 풀이 (c++)

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

25963번: 계단 만들기 (Small)

적당히 재밌어보여서 시도한 문제.

---

접근 방법

 

 너비 N의 마인크래프트 월드에서, 모든 인접한 칸의 차가 1 이하가 되도록 만드는 문제이다.

 

그리디하게 접근하고 싶었으나, 잘 떠오르지 않아서 문제 분류를 보니 dp문제였다.

dp문제이므로 완전탐색으로 풀 수 있는 방법을 먼저 생각했다.

 

특정 블럭을 다른 위치로 옮긴다고 생각하지말고, 해당 위치에서 양 옆칸의 높이차를 맞추기 위해 블럭을 빼거나 쌓는다고만 생각하자.

 

특정 위치에서 블럭은 최대 99개까지 빼거나, 쌓을 수 있다.

물론 블럭의 최대 갯수와 평균치가 존재하므로 99개보다는 낮지만, 메모리 최적화가 필요 없으므로 그렇다고 생각하자.

 

맨 앞 칸에서 블럭의 높이를 h로 설정해주면, 다음 칸의 높이는 h-1, h, h+1 셋 중 하나이다. 

그렇게 마지막 칸 까지 블럭의 높이를 조절하고, 블럭의 총 개수가 일치하는지 센다.

 

dp[idx][height][sum] = idx번째 블럭의 높이를 height로 설정하고, 사용한 블럭의 개수가 sum일때 블럭을 제거/쌓는 최솟값

 

그리고 블럭을 옮기는 것이 아니라 블럭의 + / - 변화의 개수를 더했으므로, 마지막에 2로 나누어준다.

 

---

풀이

 

tag : dp

#include<iostream>
#include<string.h>
#define INF 0x3f3f3f3f
using namespace std;
int N, cnt = 0;
int arr[200];
int dp[101][101][5100];

int solve(int idx, int height, int sum){
  //idx를 height으로 설정하고, 총 사용 블럭이 sum개일때 최솟값

  if(idx==N-1)
    return (sum == cnt) ? 0 : INF;

  int &ret = dp[idx][height][sum];
  if(ret!=-1)
    return ret;
  ret = INF;

  /** idx+1 번째 블럭의 높이*/
  ret=min(ret,solve(idx+1,height,sum+height)+abs(height-arr[idx+1])); //같게
  if(height<100)
    ret=min(ret,solve(idx+1,height+1,sum+height+1)+abs(height+1-arr[idx+1])); //하나 크게
  if(height>0)
    ret=min(ret,solve(idx+1,height-1,sum+height-1)+abs(height-1-arr[idx+1])); //하나 작게
  return ret;
}
int main(){
  cin >> N;
  for (int i = 0; i < N;i++){
    cin >> arr[i];
    cnt += arr[i];
  }

  int ans = INF;
  memset(dp, -1, sizeof(dp));
  for (int i = 1; i <= 100;i++)
    ans = min(ans, solve(0, i, i)+abs(arr[0]-i));
    
  cout << ans/2;
}