코드업[3321]- 최고의 피자🍕

https://codeup.kr/problem.php?id=3321

 

처음에 문제를 잘못읽어서 '엥 그냥 더하면 되는거 아닌가'했다! 그럴리가 없지!

 

토핑의 가격이 모두 같으니, 토핑의 칼로리가 크면 클수록 1달러 당 열량의 수가 클 것이다

ex) 토핑 A: 칼로리 200 가격 2  --> 1달러당 열량: 200/2=100 

      토핑 B: 칼로리 10    가격 2  --> 1달러당 열량: 10/2= 5

그러니 칼로리가 높은 토핑부터 더하면서 [1달러당 열량의 수]를 비교해보면 된다. 

 

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc=new Scanner(System.in);
		int num=sc.nextInt();
		int doughCost=sc.nextInt();
		int tCost=sc.nextInt();
		
		int doughCal=sc.nextInt();
		Integer cal[]= new Integer[num];
		for(int i=0;i<num;i++) {
			cal[i]=sc.nextInt();
		}
		
		Arrays.sort(cal,Collections.reverseOrder());

		int bCal=doughCal;
		int bCost=doughCost;
		int before=bCal/bCost;
		
		int aCost=bCost;
		int aCal=bCal;
		int after=0;
		for(int i=0;i<num;i++) {
			aCost+= tCost;
			aCal+=cal[i];
			after=aCal/aCost;
			before=bCal/bCost;
			
			if(before>after)
				break;
			else {
				bCal=aCal;
				bCost=aCost;
			}
			
		}

		int answer=before;
		System.out.println(answer);
	}
		
}

 도우는 항상 존재해야하기 때문에 피자의 default 칼로리와 가격은 도우의 칼로리와 가격으로 시작한다.

토핑을 하나씩 추가하기 전(before, bCost, bCal)과 후의 상황(after, aCost, aCal)으로 구성하였다. 

토핑을 이전보다 하나씩 추가했는데 [1달러당 열량수]가 작아졌다면 그 이전의 상황이 가장 best일 것이다.