[백준 / BOJ] 19942 다이어트

문제

출처 : www.acmicpc.net/problem/19942

19942번: 다이어트

식재료 N개중 몇개를 선택해서 이들의 영양분(단백질 탄수화물 지방 비타민)이 일정이상이 되어야한다. 각 식재료에는 가격이있다. 이때, 가격을 최소로하는 식재료 조합을 찾는 문제였다.

---

풀이

완전탐색으로 풀은 문제다.

탐색마다 영양소를 선택하는 경우, 선택하지 않는경우로 총 2가지 선택지가 있으므로, 최대 반복횟수는 2^15가 된다.

 

풀이는 간단한데, 

단백질 탄수화물 지방 비타민 이 있을때, 각각의 영양소가 모두 일정이상이 될때까지 재귀를 돌리면된다.

 

최소비용 식재료를 출력하는 부분을 구현하는게 힘들었는데, 나는 재귀 함수안에 string 변수를 만들어서 영양소의 번호를 string에 이어줬다.

예를들어, 지금까지 1번 3번 영양소를 선택했고, 이번에 7번 영양소를 선택했다면, 

string = 137 이 된다. 

이후에, 9 번영양소를 선택하면

string = 1379 가 된다.

마지막에 모인것들을 출력하면됨

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/19942%20%EB%8B%A4%EC%9D%B4%EC%96%B4%ED%8A%B8/main.cpp

devxb/JJUNalgo