[BOJ]2315 : 가로등 끄기(c++)

[문제] : https://www.acmicpc.net/problem/2315

[풀이]

재귀함수로 현재 마징가의 위치, 현재 꺼진 가로등중 (맨 오른쪽 가로등 + 1) 과 (맨 왼쪽 가로등 - 1)의 위치, 현재까지 킨 가로등의 개수, 자신의 위치가 오른쪽인가 왼쪽인가를 판별하는 변수, 현재 켜진 가로등이 소비하는 전체 전력을 매개변수로 받았다. 마징가는 현재위치에서 오른쪽이나 왼쪽 가로등으로 이동해야 하는데 이때 가로등을 항상 키는게 이득이므로 마징가가 지나간 경로의 가로등은 항상 꺼지게 된다. 따라서 rightpos와 leftpos 변수 만으로도 현재 상태를 나타낼 수 있게 된다. 또한 반드시 하나의 가로등을 키게끔 움직이므로 마징가의 위치는 현재 꺼진 가로등중에서 맨 오른쪽 아니면 맨 왼쪽에 위치하게 된다. 따라서 cache[1001][1001][2]의 메모리만으로 현재 상태를 저장할 수 있다. 마징가가 자신의 오른쪽에 켜진 가로등을 끄는 경우와 왼쪽에 켜진 가로등을 끄는 경우 중 작은 값을 반환하게 하고 만약 범위를 벗어났다면 INF를 리턴, 가로등을 모두 껏다면 0이 리턴되게 하였다.

[코드]

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
#include <math.h>
#define INF 1000000001
using namespace std;

long long cache[1001][1001][2];
int N;
vector<pair<int, int>> p;

long long DP(int curpos, int rightpos, int leftpos, int num, int flag, int total)
{
	if (num >= N) return 0;
	if (curpos < 0 || curpos >= N) return INF;
	long long& ret = cache[rightpos][leftpos][flag];
	if (ret != -1) return ret;
	long long res1 = INF, res2 = INF;
	if(rightpos < N)
		res1 = DP(rightpos, rightpos + 1, leftpos, num + 1, 0,total - p[rightpos].second) 
			+ abs(p[curpos].first - p[rightpos].first) * total;
	if(leftpos >= 0)
		res2 = DP(leftpos, rightpos, leftpos - 1, num + 1, 1,total - p[leftpos].second) 
			+ abs(p[curpos].first - p[leftpos].first) * total;

	return ret = min(res1, res2);
}

int main() {

	cin >> N;
	int M;
	cin >> M;
	int t = 0;
	memset(cache, -1, sizeof cache);
	p.resize(N);
	for (int i = 0; i < N; ++i)
	{
		int a, b;
		cin >> a >> b;
		p[i] = { a,b };
		t += b;
	}

	t -= p[M - 1].second;

	cout << DP(M - 1, M, M - 2, 1, 0,t) << endl;
	return 0;
}

지적 환영합니다