백준 2839번 설탕 배달

🔒[문제 url]

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

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
using namespace std;

int n;
int dp[5001];

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
}

void SOLVE()
{
	/*
	Dynamic Programming

	N kg의 설탕을 가져갈때 필요한 봉지의 수는,
	(N-5)kg 설탕에 필요한 봉지의 수보다 1개가 더 필요하다.

	(N-5)kg 설탕을 가져갈 방법이 없는 경우,
	(N-3)kg 설탕에 필요한 봉지의 수보다 1개가 더 필요하다.

	(N-3)kg 설탕또한 가져갈 방법이 없는 경우, N kg 설탕을 가져갈 방법도 없다.

	*/ 

	// 초기 설정
	dp[3] = 1; dp[4] = 0; dp[5] = 1;

	// Bottom Up DP
	for (int i = 6; i <= n; i++)
	{
		/*
		i - 5를 반드시 먼저 봐야한다.
		i - 3을 먼저 볼 경우,
		예를 들어 N == 15인 경우에
		5 5 5가 아닌 3 3 3 3 3으로 계산되어 오류가 발생한다.
		*/
		if (dp[i - 5]) dp[i] = dp[i - 5] + 1;
		else if (dp[i - 3]) dp[i] = dp[i - 3] + 1;
		else dp[i] = 0;
	}

	// 출력
	if (dp[n]) cout << dp[n];
	else cout << -1; // dp[n] == 0
}

int main()
{
	INPUT();

	SOLVE();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.