[C/C++] 백준 - 21555번 : 빛의 돌 옮기기

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

21555번: 빛의 돌 옮기기

문제

폴리매스 왕국의 중앙에 위치해 있는 빛의 돌은 사람들에게 빛을 공급합니다. 빛의 돌은 거리 L$L$만큼 떨어진 곳까지 빛을 공급할 수 있습니다. 빛의 돌의 세기가 점점 약해지고 있기 때문에, 사람들은 빛의 돌의 위치를 옮겨서 모든 집에 빛의 돌이 공급될 수 있게 하려고 합니다.

빛의 돌을 옮길 위치는 이미 정해졌습니다. 문제는 빛의 돌을 옮기기 위해 큰 비용이 든다는 것입니다. 비용을 최소화하기 위해 빛의 돌을 끌고 가야 할지, 아니면 들고 가야 할지 정해야 합니다.

빛의 돌을 옮기게 될 길을 N$N$개의 구간으로 나누면, i$i$번 구간에서 빛의 돌을 끌고 가려면 Ai$A_i$의 비용이 들고, 빛의 돌을 들고 가려면 Bi$B_i$의 비용이 듭니다. 또한, 빛의 돌을 옮기는 방식을 바꿀 때마다 K$K$의 추가 비용이 듭니다. (맨 처음과 맨 끝에는 추가 비용 K$K$가 들지 않습니다.)

예를 들어, N=3$N=3$, K=2$K=2$, A=[1,7,3]$A=[1, 7, 3]$, B=[9,3,4]$B=[9, 3, 4]$라고 합시다. 돌을 옮기는 한 가지 방법은 전체 구간에서 끌고 가는 것으로, 1+7+3=11$1+7+3=11$의 비용이 필요합니다. 반면 첫 번째 구간에서는 빛의 돌을 끌어서 옮기고, 두세 번째 구간에서는 빛의 돌을 들어서 옮기면, 1+2+3+4=10$1+2+3+4=10$의 비용이 필요하므로 더 적은 비용으로 돌을 옮길 수 있습니다.

---

빛의 돌을 옮기기 위한 최소 비용을 구해야하는 문제이다.

모든 구간의 가능한 경우의 수를 모두 확인하고 최소 비용을 구한다? : 메모이제이션을 적용하여 중복 구간을 삭제하는 동적계획법 적용

 

모든 구간을 확인하는 재귀함수 형태로 코드를 작성하고 중복된 구간의 같은 방문은 방지해야한다.

나는 메모이제이션을 cache[구간][빛의 돌을 끌고가는 경우][빛의 돌을 들고가는 경우]로 적용하였다. 같은 구간에 같은 방식으로 빛의 돌을 옮기려하는 경우를 중복하여 확인하는 것을 방지할 수 있다.

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define Mod 1000000007
#define endl '\n'

using namespace std;

int N, K;
vector<pair<int, int>> power;
long long cache[200000 + 1][2][2];

void input(){
    cin >> N >> K;
    power.resize(N);
    for(int i=0;i<N;i++) cin >> power[i].first;
    for(int i=0;i<N;i++) cin >> power[i].second;
}

long long path(int index, int method1, int method2){
    if(index == N) return 0;
    long long &ret = cache[index][method1][method2];
    
    if(ret != -1) return ret;
    ret = 0;
    if(method1 == 1) ret = min(path(index+1, method1, method2) + power[index].first,
    				path(index+1, 0, 1) + power[index].second + K);
    if(method2 == 1) ret = min(path(index+1, method1, method2) + power[index].second, 
    				path(index+1, 1, 0) + power[index].first + K);
    return ret;
}

long long solution(){
    memset(cache, -1, sizeof(cache));
    return min(path(1, 1, 0) + power[0].first, path(1, 0, 1) + power[0].second);
}

int main(){
    fastio;
    input();
    cout << solution() << endl;

    return 0;
}