[C++] BOJ 2839 ŠEĆER 설탕배달

www.acmicpc.net/problem/2839

2839번: 설탕 배달

코드

#include<iostream>
#include<algorithm>
using namespace std;
int n, dp[5005];

int main() {
	cin >> n;
	dp[1] = -1; dp[2] = -1; dp[3] = 1; dp[4] = -1; dp[5] = 1;
	for (int i = 6; i <= n; i++) {
		if (dp[i - 3] != -1 && dp[i - 5] != -1)
			dp[i] = min(dp[i - 3], dp[i - 5]) + 1;
		else if (dp[i - 3] != -1) dp[i] = dp[i - 3] + 1;
		else if (dp[i - 5] != -1) dp[i] = dp[i - 5] + 1;
		else dp[i] = -1;
	}
	cout << dp[n];
}

풀이방법

i번째 원소가 각각 i 킬로그램의 설탕을 배달할 때 봉지 몇 개를 가져가야 하는지를 나타내는 배열 dp를 만든다. 처음 i=1에서 i=5까지는 직접 입력해주고, 나머지는 DP를 이용해 푼다. i-3 킬로그램 또는 i-5 킬로그램의 설탕을 배달하는 방법이 모두 존재하는 경우, 둘 중 최솟값에 1을 더한 결과값을 dp[i]에 저장해준다. 둘 중 하나만 존재하는 경우에는 각 경우 봉지의 최솟값에 1을 더한 결과를 dp[i]에 저장해준다. 두 경우 모두 존재하지 않을 경우, i 킬로그램 역시 배달할 수 없기 때문에, dp[i]에는 -1값을 저장한다. 이 과정을 for문을 이용해 i=n까지 반복한 뒤 dp[n]값을 출력해준다.

고민과정

이게 어떤 면에서 그리디한 건지 모르겠다. 그냥 보자마자 DP가 제일 나을 것 같아서 DP로 풀었다.