[C++] 백준 2839 - 설탕 배달

August 7, 2024

🔐 백준 2839 - 설탕 배달

처음 문제를 보았을 때, 그리디와 DP의 두 가지 방법으로 풀 수 있겠다는 생각을 하였다.

만약 설탕이 5의 배수로 주어진다면 굳이 3킬로그램 봉지를 쓸 필요가 없을 것이며, 설탕이 0이 될

때까지 3을 빼면서 5의 배수인지를 확인하는 그리디한 풀이를 써도 되겠지만, DP로 풀고 싶었다.

따라서 설탕 i킬로그램 배달을 위한 최소 봉지 개수를 저장할 dp 배열을 만들고, i-3과 i-5에

해당하는 dp 배열값을 비교하여 최솟값 + 1로 초기화해 주었다. 주의해야 할 점은 3, 5 짜리 봉지로

만들 수 없는 수가 주어졌을 때인데, 처음 배열을 5000으로 초기화시켜 배달이 불가능한 수에 대한

예외처리를 한 러프한 풀이를 사용하였다. (좋은 풀이가 아님) 초기 배열의 값을 -1로 두고, i-3, i-5에

대해 -1인지 아닌지를 판단하는 if문을 통해 예외처리를 할 수도 있을 것이다.

(여러가지 풀이가 존재 가능)

dp[i] = min(dp[i-3], dp[i-5]) + 1;