[BOJ 25499 // C++] Tipover Transform

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 25499번 문제인 Tipover Transform이다.
문제는 아래 링크를 확인하자.

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

25499번: Tipover Transform

주어지는 모든 블록은 결국 모두 적어도 한 번씩은 밟고 지나가야 함을 관찰하자.

 

위 관찰에 따라, 각 블록이 쓰러진 방향에 대하여 해당 블록의 왼쪽 끝까지 도달하기 위해 필요한 최소 큐브블록 개수를 이전 블록의 쓰러진 방향에 따른 각 상태의 왼쪽 끝까지 도달하기 위해 필요한 큐브블록의 수를 이용해 나타낼 수 있음을 알 수 있다. 즉, 이전 블록의 (쓰러진 방향에 따른) 왼쪽 끝까지 도달하기 위해 필요한 최소 큐브블록 개수와 현재 블록의 (쓰러진 방향에 따른) 왼쪽 끝까지 도달하기 위해 필요한 최소 큐브블록 개수 사이에는 점화관계가 존재함을 알 수 있다.

 

이와 같은 점화관계를 이용해 dp로 문제를 해결해주자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

int N, M;
pair<int, int> seg[300001][3]; // 0: 서있음, 1: 왼쪽쓰러짐, 2: 오른쪽쓰러짐
int dp[300001][3];
int ans = 1000000007;

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

	seg[0][0] = seg[0][1] = seg[0][2] = { 0,0 };

	cin >> N;
	for (int i = 1; i <= N; i++) {
		int h; cin >> h;
		if (h) {
			M++;
			seg[M][0] = { i,i };
			seg[M][1] = { i - h,i - 1 };
			seg[M][2] = { i + 1,i + h };
		}
	}

	for (int i = 1; i <= M; i++) {
		dp[i][0] = dp[i][1] = dp[i][2] = 1000000007;
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				if (seg[i - 1][j].second < seg[i][k].first) dp[i][k] = min(dp[i][k], dp[i - 1][j] + (seg[i][k].first - seg[i - 1][j].second - 1));
			}
		}
	}

	ans = min(dp[M][0] + (N - seg[M][0].second), dp[M][1] + (N - seg[M][1].second));
	if (seg[M][2].second <= N) ans = min(ans, dp[M][2] + (N - seg[M][2].second));

	cout << ans;
}