백준 4781 - 사탕 가게

소스 코드(C++) : https://github.com/CaChiJ/JustCodes/blob/main/Algorithm%20Solutions/DP/BOJ4781.cpp

---

👀 살펴보기

문제를 요약해보면 다음과 같다.

사탕 ${n}$종류가 있다. 사탕의 개수는 무수히 많다. 사탕마다 칼로리와 가격이 주어진다. 돈 ${m}$으로 구입할 수 있는 사탕들의 칼로리의 총합 중 가장 높은 것을 구하라

배낭 문제임을 쉽게 알 수 있다. 사탕의 개수는 무수히 많으므로 Unbounded Knapsack 문제이다. 단순히 가격을 DP 배열의 인덱스로 하여 풀면 될 것 같지만 입력이 심상치 않다.

각 사탕의 칼로리 ${c}$와 가격 ${p}$가 주어진다. (1 ≤ ${c}$ ≤ 5,000, 0.01 ≤ ${p}$ ≤ 100.00) c는 항상 정수, ${p}$는 항상 소수점 둘째자리이다.

가격이 실수로 들어오기 때문에 가격을 그대로 인덱스로 사용할 수는 없다. 해결 방법은 간단하다. p의 값에 100을 곱해 정수로 만들어주면 된다.

---

🧶 로직

가격을 입력받을 때 100을 곱하여 정수로 바꿔 저장한다. 이때 100을 곱한 뒤 바로 정수 자료형으로 바꾸면 부동 소수점 오차로 인해 0.10과 같은 값은 잘못된 값으로 저장될 수 있다. 따라서 반올림 후 저장해야 한다.

그 다음은 다른 배낭 문제와 다르지 않다. 다음의 식으로 DP 배열을 갱신해 나간다.

// p[k] : k+1번째 사탕의 가격 * 100
// c[k] : k+1번째 사탕의 칼로리
// DP[w] : 돈 w/100으로 얻을 수 있는 칼로리의 합 중 최댓값
DP[w] = max(DP[w], DP[w-p[k]] + c[k])

자세한 내용은 필자의 소스 코드를 참고해주기 바란다.

---

⏱ 시간 복잡도

가진 돈 ${M}$에 100을 곱한 크기의 배열을 사용하지만 복잡도에는 영향이 없다. 이 문제는 ${p}$가 실수인 점 외에 기본적인 배낭 문제와 차이가 없으므로 시간 복잡도는 ${O(NM)}$이다.