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

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

코드

#include <iostream>
using namespace std;

#define FASTIO ios::sync_with_stdio(false);cin.tie(NULL);
#define MAX 2 * 100000 + 1
typedef long long ll;

int a[MAX], b[MAX], n, k;
ll dp[MAX][2];

int main() {
	FASTIO;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];

	dp[1][0] = a[1];
	dp[1][1] = b[1];

	for (int i = 2; i <= n; i++) {
		dp[i][0] = min(dp[i - 1][0] + a[i], dp[i - 1][1] + k + a[i]);
		dp[i][1] = min(dp[i - 1][1] + b[i], dp[i - 1][0] + k + b[i]);
	}

	cout << min(dp[n][0], dp[n][1]);
	return 0;
}

설명

필요한 값들을 입력받고 dp[n][k]에 직전에 k라는 방식으로 돌을 옮겨 n번째 구간까지 소모한 비용을 저장해나갑니다.

 

dp 식은 아래와 같습니다.

 

- 처음 시작할 때 

• 빛의 돌을 끌고 가기 :  dp[1][0] = a[1] 
• 빛의 돌을 들고 가기  : dp[1][1] = b[1]

- 이후

• 빛의 돌을 끌고 가기 = min(직전 구간에서 빛의 돌을 끌고 왔을 때의 최소 비용, 직전 구간에서 빛의 돌을 들고 왔을 때의 최소 비용 + 방식바꾸기) + 이번 구간에서 빛의 돌을 끌고 갈 때 드는 비용
• 빛의 돌을 들고 가기 =  min(직전 구간에서 빛의 돌을 들고 왔을 때의 최소 비용, 직전 구간에서 빛의 돌을 끌고 왔을 때의 최소 비용 + 방식바꾸기) + 이번 구간에서 빛의 돌을 들고 갈 때 드는 비용

 

 

느낀 점

빠르게 식을 세워서 한 번에 풀었습니다! 

이후 제출에서는 각각 빠른 입출력 적용, 식을 조금 더 간단하게 정리했습니다.