[백준] 5545 최고의 피자 - 그리디(Greedy, 탐욕법) + 정렬(Sort) JAVA

https://www.acmicpc.net/problem/5545

코드설명

그리디(Greedy, 탐욕법) + 정렬(Sort) 문제입니다.

 

처음에 문제를 보고, 파라매트릭 서치를 활용해야하나? 라는 생각이 떠올랐습니다.

하지만, 어떤 값을 "기준"으로 비교를 하며 진행해야하는데, "기준" (즉, 첫번쨰 값)이 존재하지 않아 해당 방식은 적용되지 않습니다.

 

두번쨰 떠오른 방법은, 오름차순 정렬을 진행한뒤 만약 현재 칼로리보다 더 추가한 토핑 이후의 칼로리가 더 작아진다면 중단합니다. 이떄, 더 작아져야만 중단해야합니다. (이 점이 맹점입니다.)

이유는 버림 문제입니다. 정수 나눗셈을 사용하기 때문에, 실제로는 약간 더 높은 값이지만 버림으로 인해 같은 값으로 계산될 수 있습니다. <=를 사용하면 이런 경우도 포함할 수 있습니다.

 

예시로 들면, 

java에서 정수 나눗셈을 할 때, 결과는 항상 내림(floor)됩니다. 이로 인해 실제로는 약간 더 큰 값이 같은 정수 값으로 계산될 수 있습니다. 예를 들어 설명하겠습니다:

1. 케이스 A: 열량 370, 가격 10 => 370 / 10 = 37
2. 케이스 B: 열량 379, 가격 10 => 379 / 10 = 37

여기서 케이스 B가 실제로는 더 높은 1원당 열량(37.9)을 가지고 있지만, 정수 나눗셈으로 인해 케이스 A와 동일한 37이라는 결과가 나옵니다.

<를 사용한다면:

• 첫 번째로 계산된 37(케이스 A)이 answer가 됩니다.
• 그 다음 케이스 B를 계산했을 때, 37 < 37는 거짓이므로 answer가 업데이트되지 않습니다.

반면 <=를 사용하면:

• 케이스 A에서 37이 answer가 됩니다.
• 케이스 B를 계산했을 때, 37 <= 37는 참이므로 answer가 업데이트됩니다.

하지만 생각해보면 문제에서는 소수점 이하는 버리고 정수 값으로 출력한다. 라는 문구가 있습니다. 그렇기 떄문에 소수점 이하는 애초에 무시하고 계산하면 되지 않을까? 싶습니다. 

 

그래서 위와 같이 문제점은 존재한다고 생각이 되나, 실제로 어떤 예제들에서 이런일이 발생할 수 있을까 생각하면 명확히는 못찾겠습니다.

 

버림의 관점에서 재밌는 문제였습니다.

코드

package Main;

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

public class Main {
    public static int N, M, C, X, A, B, DoughCalory;
    public static int answer = 0;
    public static int[] toping;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		A = Integer.parseInt(st.nextToken());
		B = Integer.parseInt(st.nextToken());
		toping = new int[N];
		
		st = new StringTokenizer(br.readLine());
		DoughCalory = Integer.parseInt(st.nextToken()); 
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			toping[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(toping, 0, toping.length);

		answer = calculateMaxCalory(toping.length, toping.length - 1);
		for(int i=N-1;i>=0;i--) {
			int calculate = calculateMaxCalory(i, toping.length - 1);
			if(answer <= calculate) {
				answer = calculate;
			}
			else if(answer > calculate) {
				break;
			}
		}
		
		System.out.println(answer);
	}
    
//    [fromIdx..toIdx]까지의 합 계산하여 반환
    public static int calculateMaxCalory(int fromIdx, int toIdx) {
    	
    	int prefixSum = DoughCalory;
    	for(int i=toIdx; i>=fromIdx; i--) {
    		prefixSum += toping[i];
    	}
    	
    	int divideBy = A + B * (toIdx - fromIdx + 1);
//    	System.out.println(prefixSum+" "+divideBy);
    	return prefixSum / divideBy;
    }
    
}