사탕 가게( BOJ 4781 )

문제

4781. 사탕 가게 : https://www.acmicpc.net/problem/4781

4781번: 사탕 가게

 

문제 파악하기

• 주어진 자금 내에서 가장 높은 칼로리를 얻을 수 있도록 사탕을 구매해야 하는 문제입니다.
• 여러모로 냅색 문제와 유사하지만 사탕을 원하는만큼 구입할 수 있다는 차이점이 있습니다.
• 그렇다고 무작정 반복문을 돌리면 3중 반복문이 나오기에 시간초과가 걸립니다.
• 수행 시간을 줄이기 위해서는 기본 냅색 문제의 점화식을 수정해야 합니다.

 

문제 해결하기

• 기본 냅색 문제는 물건이 하나만 있기 때문에 다음과 같은 점화식이 나옵니다.
  dp[i][j] = max( dp[i-1][j], dp[i-1][j-w[i]] + c[i] )
• 하지만 이번 문제에서는 사탕을 더 살 수 있기 때문에 dp[i][j-w[i]] + c[i] 의 값도 비교해야 합니다.
• 총 3가지 경우를 모두 비교하면 문제를 해결할 수 있습니다.
• 참고로 1차원 배열을 이용한 냅색문제 해결 방법을 사용하면 좀 더 효율적으로 해결할 수 있습니다.

 

후기

전형적인 냅색문제라고 생각하고 풀었다가 뒷통수 맞은 문제입니다. 냅색 문제 개념을 다질 때 풀어보면 확실해보입니다.