설탕 배달 (feat. 백준, 2839번)

설탕 배달
https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/2839
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register int N, arr[5001];
	fill(arr, arr + 5001, 999999);
	arr[3] = 1, arr[5] = 1;
	cin >> N;
	for (register int i = 6; i <= N; ++i)
		arr[i] = min(arr[i - 3], arr[i - 5]) + 1;
	if (arr[N] >= 999999)
		cout << -1 << endl;
	else
		cout << arr[N] << endl;
	return 0;
}
// *&)*@*

1. 3은 1개(3), 5는 1개(5), 6은 2개(3 * 2), 8은 2개(3, 5) 로 정의할 수 있습니다.
2. 즉 구하려는 값을 Ai라고 한다면, Ai = min(Ai-3, Ai-5) + 1이 도출됩니다.