취미로 코딩하기

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

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

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

dp[L][R][dir]을 "구간 [L,R]에 모든 번호의 램프가 꺼질 때까지의 (구간 내에 포함되지 않은 램프를 포함한 모든 램프의) 에너지 소비량의 최솟값"으로 정의하자. (단, [L,R]이 V를 포함할 때에만 정의된다.) dir은 모든 램프를 끈 뒤 가로등 L에 위치하는지 R에 위치하는지를 나타내는 변수이다. ([L,R]의 모든 램프를 에너지 소비를 최소화하며 끄는 것을 마치면 항상 L 또는 R에서 작업을 마무리함을 관찰하자.)

이 때, dp[L][R][0]은 dp[L+1][R][0]에서 (L+1번 램프의 위치에서 L번 램프까지 이동하는 동안 소비된 에너지의 양), 즉 (L+1번 램프와 L번 램프 사이 거리) * ([L+1,R]에 포함되지 않는 램프의 개수)을 더한 값과 dp[L+1][R][1]에서 (R번 램프의 위치에서 L번 램프까지 이동하는 동안 소비된 에너지의 양), 즉 (R번 램프와 L번 램프 사이 거리) * ([L+1,R]에 포함되지 않는 램프의 개수)를 더한 값 둘 중 작은 값이 된다. 이와 같은 방식으로 dp[L][R][1]에 대한 식 또한 얻을 수 있다.

각 [L,R] 구간에 대한 계산은 해당 구간이 포함하는 더 작은 크기의 구간에 대한 값만을 이용해 계산하므로 위와 같은 점화관계를 통해 문제를 충분히 해결할 수 있음을 관찰할 수 있다.

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

#include <iostream>
using namespace std;
typedef long long ll;

int N, V;
ll dp[1001][1001][2];
ll dist[1001], watt[1001];
ll psum[1001];

ll func(int L, int R, int dir) {
	if (dp[L][R][dir]) return dp[L][R][dir];

	ll& ret = dp[L][R][dir] = 1000000007;
	if (dir == 1 && R > V) {
		ret = min(ret, func(L, R - 1, 0) + (dist[R] - dist[L]) * (psum[L - 1] + psum[N] - psum[R - 1]));
		ret = min(ret, func(L, R - 1, 1) + (dist[R] - dist[R - 1]) * (psum[L - 1] + psum[N] - psum[R - 1]));
	}
	else if (dir == 0 && L < V) {
		ret = min(ret, func(L + 1, R, 0) + (dist[L + 1] - dist[L]) * (psum[L] + psum[N] - psum[R]));
		ret = min(ret, func(L + 1, R, 1) + (dist[R] - dist[L]) * (psum[L] + psum[N] - psum[R]));
	}

	return ret;
}

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

	cin >> N >> V;
	for (int i = 1; i <= N; i++) {
		cin >> dist[i] >> watt[i];
		psum[i] = psum[i - 1] + watt[i];
	}

	dp[V][V][0] = dp[V][V][1] = 1;
	cout << min(func(1, N, 0), func(1, N, 1)) - 1;
}