백준 5545번: 최고의 피자 (JAVA)

 

문제 해석

 

토핑 N개 중에서 여러 종류를 선택하는데 같은 종류는 한개만 선택할 수 있고 아무 토핑도 선택하지 않아도 된다.

피자를 1원 당 최대 열량을 내도록 하는 토핑 조합을 찾아야 한다. 토핑 가격은 모든 종류가 동일하다.

 

알고리즘

 

토핑의 가격이 모두 동일하므로 열량이 가장 큰 것부터 내림차순으로 하나씩 추가해가면서 1원 당 최대 열량이 되도록 하는 값을 찾는다. 이 문제를 풀 때 간과했는데 토핑을 하나도 선택하지 않는 것이 더 나은 경우도 체크해야 한다.

 

코드