[SWEA] 5215. 햄버거 다이어트 _ JAVA

출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-lPB6dHUDFAVT

SW Expert Academy

 

 

풀이

제한된 칼로리 조건 하에서 가장 만족도 높은 조합을 선택하면 되는 문제입니다.

부분집합의 합을 구하는 문제와 아주 비슷한 듯합니다.

부분집합의 각 원소에 대해서 해당 항목을 선택하는 경우와 선택하지 않은 경우를 재귀 함수를 통해 반복하며

가장 최적의 해를 찾을 수 있도록 완전탐색하였습니다.

 

조건으로는 정해진 칼로리를 초과한 경우를 제외시켰으며, 

주어진 N번째 항목까지 모두 탐색한 경우에 대하여 ( cnt == N )

선호도가 가장 높은 경우를 ans 변수에 저장한 뒤 모든 탐색이 끝난 뒤 출력하여 답을 찾았습니다.

 

탐색을 하면서 만족도와 현재까지의 칼로리를 계속 기록하며

                 선택한 경우 --> 해당 항목의 만족도와 칼로리를 더해준 뒤 진행하고

                 선택하지 않은 경우 --> 기존의 상태에서 다음 번째 항목으로 넘겨주는

위 과정만 이해하신다면 유사한 문제들을 쉽게 풀이할 수 있을 것으로 보입니다.

 

 

코드