#5545 : 최고의 피자

풀이방법

사용된 것:

TreeSet

정렬

그리디

 

 

 

2022.11.09

이 문제의 경우, 모든 경우의 수에 대하여 1원당 열량을 구하는 것이 매우 쉽다.

그 이유는 다음과 같다.

• 토핑의 종류가 최대 100가지밖에 안 된다.
• 동일한 토핑을 여러 번 올리는 경우가 없다.
• 토핑의 가격이 모두 같으므로, 열량이 더 높은 토핑을 올리지 않은 채 열량이 더 낮은 토핑을 올린다면 무조건! 손해이다. 그러므로 가장 열량이 높은 토핑부터 골라잡는 게 무조건 이득이다.

 

따라서 모든 경우의 수에 대한 1원당 열량 값을 싹 다 구하고, 그 중 가장 큰 것을 출력하면 된다.

방법은 다음과 같다.

 

먼저 토핑의 값을 모두 읽어온 뒤 오름차순 또는 내림차순으로 정렬해놓는다.

 

아무 토핑도 올리지 않았을 경우의 1원당 열량을 계산하여 그 값을 TreeSet에 넣어둔다.

 

그 다음에는 반복문을 이용하여

가장 열량이 높은 토핑부터 하나씩 누적하여 피자에 추가해 간다.

토핑이 하나 추가될 때마다 변동되는 가격과 총 열량을 계산하여, 현재의 1원당 열량을 TreeSet에 넣는다.

 

반복문이 끝나고 나면 TreeSet에는 가능한 모든 경우의 수의 1원당 열량 값이 오름차순 정렬되어 들어가있게 된다.

 

TreeSet의 가장 끝에 있는 값을 last() 메소드로 꺼내어 화면에 출력하면 문제가 해결된다.

 

 

코드

Java(2022.11.09)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		/*
		 * 입력값 받아오기
		 */
		
		//토핑의 종류 수
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer (br.readLine());
		
		//도우 가격, 토핑 하나당 가격
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		
		//도우의 열량
		int c = Integer.parseInt(br.readLine());
		
		//토핑별 열량
		int[] toppings = new int[n];	
		for(int i=0; i<n; i++) toppings[i] = Integer.parseInt(br.readLine());
		
		//토핑별 열량 오름차순 정렬
		Arrays.sort(toppings);
		
		/*
		 * 최고의 피자 찾기
		 */
		//각 경우에 대하여 계산한 1원당 열량을 모두 집어넣을 TreeSet
		TreeSet<Integer> ts = new TreeSet<Integer>();
		
		//가장 열량이 높은 토핑부터 하나씩 누적하여 추가하면서 계산
		int sum = c;	//현재까지 쌓인 열량
		int price = a;	//현재까지 쌓인 가격
		
		//아무 토핑도 올리지 않았을 때의 경우도 TreeSet에 넣어두기
		ts.add((int)Math.floor(sum/price));
		
		for(int i= n-1; i>=0; i--) {	//가장 열량이 큰 토핑부터
			sum += toppings[i];	//열량 추가
			price += b;			//가격 추가
			
			//1원당 열량을 TreeSet에 넣기
			ts.add((int)Math.floor(sum/price));
		}
		
		//정답 출력
		System.out.print(ts.last());

	}

}