[백준알고리즘] 2839번: 설탕 배달 -Python, C++

[백준알고리즘] 2839번: 설탕 배달 -Python, C++

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

2839번: 설탕 배달

설탕 n만큼을 최소의 묶음을 챙겨서 가져갈 수 있는 방법은 최대한 5의 묶음을 많이 가져가는 것이다. 5묶음을 가져갈 수 있으면서 나머지가 3묶음으로 모두 챙길 수 있다면 그게 최소로 챙겨가는 것이다.

 

n = int(input())
for i in range(n//5, -1, -1):
    t = 5*i
    if (n-t)%3 == 0:
        print(i+(n-t)//3)
        exit()
print(-1)

 

추가한 C++ 코드이다.

C++ 작성 시에는 위와 같은 방법이 아닌, 동적계획법을 사용했다. 모든 경우의 수에서 가져갈 수 있는 최소 봉지 수를 계산한 다음 해당하는 무게일 때의 봉지의 개수를 출력해준다.

 

#include <iostream>

int main(void)
{
	int n;
	std::cin >> n;

	int dp[5001];
	std::fill_n(dp, 5001, -1);

	dp[3] = 1;
	dp[5] = 1;
	for (int i = 6; i <= 5000; i++)
	{
		if (dp[i - 3] == -1 && dp[i - 5] == -1) continue;
		if (dp[i - 3] == -1)
			dp[i] = dp[i - 5] + 1;
		else if (dp[i - 5] == -1)
			dp[i] = dp[i - 3] + 1;
		else
			dp[i] = (dp[i - 3] < dp[i - 5] ? dp[i - 3] : dp[i - 5]) + 1;
	}

	std::cout << dp[n];
	return 0;
}

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다