[BOJ 3286 // C++] SHELVES

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

 

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

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

3286번: SHELVES

같은 열의 두 높이 h1 < h2에 대하여, h2의 높이에 물건을 집을 수 있다면 h1의 높이에 있는 물건 또한 집을 수 있음을 관찰할 수 있다. 따라서 같은 열에 물건이 여럿 있다면 더 높은 위치에 있는 물건만을 고려해 문제를 풀어도 충분하다. 그러므로 이제부터는 각 열마다 접근해야 하는 가장 높은 위치(없다면 0)만을 고려해 문제를 해결하도록 하자.

 

dp[r][c]를 "c열에서 높이 r까지 접근 가능한 사다리를 설치한 경우, c열 이하의 모든 열의 꺼내야 할 물건을 모두 꺼내기 위한 최소비용"으로 정의하자.

 

이 dp[r][c]의 값은 (1) c열에 설치한 높이 r의 사다리가 c열에 있는 물건에 접근할 수 있는지, 접근할 수 있다면 (2) c-1열에 있는 물건 또한 접근할 수 있는지의 여부에 따라 c-1, c-2열의 dp값을 이용해 계산해낼 수 있음을 관찰할 수 있다.

 

위 관찰을 이용해 dp[r][c]의 값을 구해내는 점화식을 찾아 문제를 해결하자.

 

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

#include <iostream>
using namespace std;

int R, C, N;
int col[102];
int dp[101][102];

int ans = 1000000007;

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

	cin >> C >> R >> N; C++;
	while (N--) {
		int A, B; cin >> A >> B; A++;
		col[A] = max(col[A], B);
	}

	for (int r = 0; r <= R; r++) {
		dp[r][0] = dp[r][1] = r;
		for (int c = 2; c <= C; c++) {
			dp[r][c] = 1000000007;
		}
	}

	//dp[r][c] : c열에 r짜리 막대를 놓은 상황. 이 때 c열까지를 완전히 채울 때의 최솟값
	for (int c = 1; c <= C; c++) {
		for (int r = 0; r <= R; r++) {
			if (r < col[c]) {
				for (int rr = col[c]; rr <= R; rr++) {
					dp[r][c] = min(dp[r][c], dp[rr][c - 1] + r);
				}
			}
			// 아래는 이제 r>=col[c] 성립
			else if (r < col[c - 1]) {
				for (int rr = 0; rr <= R; rr++) {
					dp[r][c] = min(dp[r][c], dp[rr][c - 1] + r);
				}
			}
			else {
				for (int rr = 0; rr < R; rr++) {
					dp[r][c] = min(dp[r][c], dp[rr][c - 2] + r);
				}
			}
		}
	}

	for (int r = 0; r <= R; r++) ans = min(ans, dp[r][C]);

	cout << ans;
}