백준2315 가로등 끄기

문제 링크

http://icpc.me/2315

사용 알고리즘

시간복잡도

O(n²)

풀이

dp문제입니다만, 점화식을 흔치 않은 방법으로 채우는 문제입니다.
가장 많이 나왔던 형태는 dp[i-1]를 구한 뒤 dp[i]를 구하는, 뒤에 하나씩 붙이는 방법이였습니다. 전체 공간을 한 점에서 잘라 왼쪽과 오른쪽에서 각각 계산하는 방법도 있었습니다.
그러나 이 문제는 왼쪽과 오른쪽, 양 방향으로 하나씩 채워나가는 방식을 사용합니다.

몇 가지 성질을 알아봅시다.

마징가는 1m/s로 이동하며 가로등을 끄는 역할을 수행합니다. 가로등을 끄는데 걸리는 시간은 무시합니다.
이 말은 어떤 가로등의 위치를 지난다면, 그 가로등은 끄는 것이 좋다는 것을 의미합니다.
1번 성질에 의해 i번째와 j번째 가로등이 꺼져있다면, i와 j 사이에 있는 모든 가로등이 꺼져있다고 봐도 좋습니다.

dp[i][j] = 현재 i~j번째 가로등이 꺼져있을 상태에서 정답 으로 정의를 해놓고 문제를 풀어봅시다.
i~j 범위의 가로등이 꺼져있다면, 현재 마징가의 위치는 i번째 혹은 j번째인 것은 자명한 사실입니다. 그러므로 다음으로 끌 수 있는 가로등은 i-1번째 혹은 j+1번째입니다.
현재 위치가 i인지 j인지 구분하기 위해 dp배열을 다시 정의합시다.
dp[i][j][flag] = 현재 i~j번째 가로등이 꺼져있을 상태에서 정답. 단, flag가 0인 경우 i, 1인 경우 j에 위치

i~j가 꺼져있다는 것은 1 ~ i-1와 j+1 ~ n범위는 켜져있다는 것을 의미합니다. 그리고 마징가는 초속 1m/s로 이동합니다. 구간의 합을 빠르게 구하기 위해 prefix sum을 만들어 가로등의 위치에 대한 누적합을 구해줍시다.
now : 현재 위치, pos[i] : i번째 가로등의 위치, sum[i] : 위치 누적합 이라고 각각 정의합시다.
on이라는 변수를 하나 만들어서 sum[n] - sum[j] + sum[i-1]을 저장해줍시다. 이는 1 ~ i-1와 j+1 ~ n범위의 거리를 저장합니다.
점화식은 아래와 같은 식으로 채울 수 있습니다.

(i-1 >= 1) 인 경우 : dp[i-1][j][0] + (pos[now] - pos[i-1]) * on
(j+1 <= n) 인 경우 : dp[i][j+1][0] + (pos[j+1] - pow[now]) * on
모두 가능한 경우 : 둘 중 최솟값

상태 공간이 O(n²), 각 상태에 대해 상수 시간 안에 구할 수 있으므로 O(n²)이 나옵니다.

전체 코드는 아래에 있습니다.

전체 코드

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll dp[1010][1010][2];
int n, m;
vector<ll> pos, arr, sum;

ll solve(int left, int right, int flag){
	if(left == 1 && right == n) return 0;
	ll &res = dp[left][right][flag];
	if(res != -1) return res;

	int now = flag?right:left;
	ll on = sum[n] - sum[right] + sum[left-1];
	if(left-1 >= 1){
		ll tmp = solve(left-1, right, 0) + (pos[now] - pos[left-1]) * on;
		if(res == -1 || res > tmp) res = tmp;
	}
	if(right+1 <= n){
		ll tmp = solve(left, right+1, 1) + (pos[right+1] - pos[now]) * on;
		if(res == -1 || res > tmp) res = tmp;
	}

	return res;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;

	pos.resize(n+1); arr.resize(n+1); sum.resize(n+1);

	for(int i=1; i<=n; i++){
		cin >> pos[i] >> arr[i];
		sum[i] = sum[i-1] + arr[i];
	}

	memset(dp, -1, sizeof(dp));
	cout << solve(m, m, 0);
}