[백준] 20115 에너지 드링크 - 그리디(탐욕법, Greedy) JAVA

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

20115번: 에너지 드링크

코드설명

그리디 문제입니다.

 

처음에 틀린방식으로 푼 방법은,2 3 6 9 10 가 있다고 가정합니다.

이때 (2, 3) 을 비교 (4, 6) 을 비교, (8, 9) 를 비교 (13, 10) 을 비교하여 16.5 로 만들어서 틀렸습니다.

 

위의 방식처럼하면, 최대값이 나오지 않습니다.

 

2, 3, 6, 9, 10 이있다고 가정했을때,

10 을 최대값으로 두고, 나머지 (2, 10), (3, 11), (6, 12.5) (9, 15.5) (20) 으로 나오게해야합니다.

 

즉, 가장 많은 에너지 드링크 1개를 선택하고, (여기서는 10의 양) 나머지 작은 에너지 드링크들을 해당 에너지 드링크에 모두 넣는 것 입니다.

 

처음에 진행했었던 방식에는 모순이 존재합니다. 예를 들어 7, 8, 9 가 존재한다고 가정합니다.

1. (7, 8) -> 8 + 7/2 = 11.5

2. (11.5, 9) -> 11.5 + 4.5 = 16.0 입니다.

 

만약 가장 큰 음료수병에 나머지 음료들을 더하는 방식으로 한다면, 아래와 같습니다.

1. (9, 7) -> 9 + 3.5 = 12.5

2. (12.5, 8) -> 12.5 + 4 = 16.5

 

16.5로 최적의 방안이 더 큰 결과값을 나타냅니다. 이는 작은 음료끼리 섞이면서 음료가 커지고 그 값들이 커져서 버리지 않아도 될 음료들이 버려지기 때문입니다. 더해지는 과정에서 합쳐지는 음료의 버리는 크기를 가장 적게 할 수 있는 방법입니다.

코드

정답코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	public static int N;
	public static double[] arr;
	public static double max = 0;
	public static double result = 0;
    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());
    	arr = new double[N];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    		if(max < arr[i]) {
    			max = arr[i];
    		}
    	}
    	result = max;
    	for(int i=0;i<N;i++) {
    		if(max == arr[i]) continue;
    		result += arr[i]/2;
    	}
    	
    	System.out.println(result);
    }
    
}

 

정답코드 2입니다.

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 {
	private static int N, M, Q, K;
    private static double[] arr;
    private static int answer = 0;
    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());
        
        arr = new double[N];
        for(int i=0;i<N;i++) {
        	arr[i] = Double.parseDouble(st.nextToken());
    	}
        
        Arrays.sort(arr);
        System.out.println(func());
    }
    
    public static double func() {
    	double max = 0;
    	for(int i=0; i<N; i++) {
    		max = Math.max(max, arr[i]);
    	}
    	double result = max;
    	for(int i=0;i<N;i++) {
    		if(max == arr[i]) continue;
    		result += arr[i]/2;
    	}
    	return result;
    }
}

처음에 틀린 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	public static int N;
	public static Integer[] arr;
    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());
    	arr = new Integer[N];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	Arrays.sort(arr);
    	
    	for(int i=0;i<N-1;i++) {
    		System.out.println(" arr[i]"+arr[i]);
    		arr[i+1] += arr[i] / 2;  
    	}
    	System.out.println(arr[N-1]);
    }
    
}