백준 4781번 사탕 가게

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

비교적 쉬운 DP 문제였지만 double형으로 주어진 돈의 양과 가격을 자연수로 바꾸는 것이 핵심이였습니다.

소수점 두 번째 자리까지 주어지니까 100을 곱하여 자연수로 만드는데 반올림을 위해 0.5를 더해주지 않으면 AC 처리를 받지 못하므로 0.5를 꼭 더해줘야합니다!

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 5000 + 1;

 

int N, C; //사탕 종류의 수, 칼로리

double M, P; //돈의 양, 사탕 가격

pair<int, int> candy[MAX];

int cache[100 * 100 + 1];

 

int maxCalorie(int cash)

{

        int &result = cache[cash];

        if (result != -1)

                 return result;

 

        result = 0;

        for (int i = 0; i < N; i++)

        {

                 //잔여금액을 초과해서 살 수 없다

                 if (cash - candy[i].second >= 0)

                         result = max(result, candy[i].first + maxCalorie(cash - candy[i].second));

        }

        return result;

}

 

int main(void)

{

        while (1)

        {

                 memset(cache, -1, sizeof(cache));

                 cin >> N >> M;

                 if (N == 0 && M == 0.00)

                         break;

 

                 for (int i = 0; i < N; i++)

                 {

                         cin >> C >> P;

                         candy[i] = make_pair(C, (int)(P * 100 + 0.5)); //소수점 없애기 위해 *100, 반올림 위해 + 0.5

                 }

                 cout << maxCalorie((int)(M * 100 + 0.5)) << endl; //마찬가지로 소수점 없애기 위해 *100, 반올림 위해 + 0.5

        }

        return 0;

}

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~