[백준 4781번] 사탕 가게 (C++)

문제링크 : https://www.acmicpc.net/problem/4781

4781번: 사탕 가게

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[5001], cost[5001], dp[10001];
int N, M;
float f; //소수점 대비

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    while(1)
    {
        cin >> N >> f;
        M = f*100+0.5; //소수점 처리
        if(N==0 && M==0) break;
        int result = 0;
        memset(dp, 0, sizeof(dp));
        for(int i=0; i<N; i++)
        {
            float f2;
            cin >> arr[i] >> f2;
            cost[i] = f2*100; //소수점 처리
        }
    
        for(int i=0; i<N; i++) //사탕
        {
            for(int j=0; j<=M; j++) //비용
            {
                if(j-cost[i] >= 0) dp[j] = max(dp[j], dp[j-cost[i]] + arr[i]); 
                result = max(result, dp[j]); //최대비용 저장
            }
        }
        cout << result << "\n";
    }

    

    return 0;
}

배낭 문제에 대한 이해도가 부족하다고 생각되어 추가로 골라서 푼 배낭 문제이다.

배낭 문제 보다 다른 부분에서 상당히 애를 먹었다.

 

해당 문제에서 하나는 정수로 입력받고, 하나는 소수 둘째자리까지 입력을 받는다.

소수 둘째자리까지 입력받은 것을 다시 정수로 바꿔줘야 하는데,

이를 위해 비용과 관련된 M과 cost[i]의 값을 전부 100을 곱해준다.

여기서 100을 곱해주는 것으로 끝나는 것이 아니라,

부동소수점 문제로 인해 정확히 변환되지 않을 가능성이 있어서 0.5를 추가로 더해줘야 한다.

 

그리고 케이스가 여러가지이기 때문에 dp배열과 결과값을 담을 result의 값을 매 탐색마다 초기화해주는 것도 잊어서는 안된다.

 

이후로는 최대 비용만 찾으면 되므로 가능한한 크게 담아주고 이후 최대값을 따로 저장하여 출력해준다.