[알고리즘] 백준 5545 최고의 피자 Java

문제 정보

플랫폼 : 백준
분류 : 그리디 알고리즘
난이도 : 실버3
링크 : https://www.acmicpc.net/problem/13305

입력 데이터와 시간제한 검증

입력 데이터 갯수 : 100개가량
O(nlogn) 풀이 : 시간제한 ok (정렬 사용)
모든 토핑의 열량이 10,000이라고 해도, 최대 토핑 갯수 100개를 곱하면 100만이므로 int 사용가능

풀이

주머니 사정이 얇아진 상근이.. 나와 비슷하다.
임의의 토핑을 넣었을 때, 가격당 칼로리가 제일 높은 경우를 선택하면 된다. 모든 경우의 수를 탐색하면 2^10000이 나오므로.... 현명하게 풀어보자.

1. 토핑의 칼로리를 내림차순으로 정렬한다.
2. 정렬된 토핑을 0개 ~ n개까지 추가해보면서, 1원당 칼로리가 이전 계산 결과보다 낮아지면 종료한다. (1번에서 칼로리를 내림차순으로 정렬했으므로, 그 뒤는 계산할 필요가 없다.)

우선, 입력을 받는다. 그다음에 토핑 칼로리 리스트를 내림차순으로 정렬해준다.

Arrays.sort(Array)
를 통해 오름차순으로,
Arrays.sort(Array, Collections.reverseOrder())
를 통해 내림차순으로 정렬 가능하다.

이후, 토핑을 추가해보면서, 이전것보다 작으면 break (#27)을 하고, 이전까지의 1원당 칼로리를 출력해주면 된다.

코드

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // 토핑의 갯수
		
		// 토핑의 칼로리 리스트, 내림차순 정렬을 위해 int[]가 아닌 래퍼 클래스인 Integer[]로 선언했다.
		Integer[] topKCal = new Integer[n]; 
		
		int doughPrice = sc.nextInt(); // 도우의 가격
		int topPrice = sc.nextInt(); // 토핑의 가격
		int doughKCal = sc.nextInt(); // 도우의 칼로리
		for(int i = 0; i < n; i++) 
			topKCal[i] = sc.nextInt();
		
		int ans = doughKCal / doughPrice; // 토핑을 0개 넣은 경우, 도우의 칼로리당 가격이다.
		
		Arrays.sort(topKCal, Collections.reverseOrder());
		
		int tmpPrice = doughPrice;
		int tmpKCal = doughKCal;
		for(int i = 0; i < n; i++) {
			tmpPrice += topPrice;
			tmpKCal += topKCal[i];
			int tmpAns =  tmpKCal / tmpPrice;
			if(ans > tmpAns) {
				break;
			}else {
				ans = tmpAns;
			}
		}
		System.out.println(ans);
	}
}

더 많은 정답 코드

블로그를 쓰기 이전에 풀어본 문제들이 많다. 해설강의는 없지만, 백준 문제의 풀이 코드가 필요한 경우 이곳을 클릭하여 소스코드를 참조해보도록 하자. 단, 코드만 복사-붙여넣기 하는것은 본인에게 결코 도움이 되지 않는다. 반드시 먼저 생각해보고, 막히는 경우에 참고하고 왜 이렇게 코드가 작성됐는지를 다시 한 번 생각해보는 습관을 들이자.