[백준] 20300 서강근육맨 - 그리디(탐욕법, Greedy) + 정렬(Sort) JAVA

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

20300번: 서강근육맨

코드설명

그리디 문제입니다.

 

문제예시로

5

1 2 3 4 5 가 있다고 가정합니다.

 

근손실 최소값을 구하기 위해서는 가장 큰 숫자와 가장 작은 숫자의 합이 최소값일 것입니다.

그러기 위해서 오름차순 정렬을 하면, 첫번째 숫자와 끝자리 숫자와의 합이 최소값입니다.

 

N이 짝수라면, 가장 큰 숫자도 같이 짝을 이루고,

N이 홀수라면,  마지막 숫자는 짝을 이루지 않습니다.

 

둘째 줄에는 각 운동기구의 근손실 정도를 나타내는 정수 T의 범위가 0 <= t <= 10^18 이기에 Long type을 활용해야합니다. 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
 
public class Main {
	
	public static int N;
	public static long[] arr;
	public static long 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 long[N];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Long.parseLong(st.nextToken());
    	}
    	Arrays.sort(arr);
    	
    	
    	result = arr[N-1];
    	long a = 0;
    	long b = 0;
    	if(N == 1) {
    		System.out.println("1");
    		return ;
    	}
    		
    	for(int i=0;i<N/2;i++) {
    		a = arr[i];
    		if(N%2 == 0) {
    			b = arr[N-1-i];	
    		}else if(N%2==1) {
    			b = arr[N-1-1-i];
    		}
    		result = Math.max(result, a + b);
    	}
    	System.out.println(result);
    	
 
    }
    
}

 

더 직관적인 코드입니다.

홀수라면, 가장 큰값은 혼자 운동하도록 처리합니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeMap;
 
public class Main {
	private static int N, M, Q, K;
    private static long[] 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());
        
        arr = new long[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) {
        	arr[i] = Long.parseLong(st.nextToken());
        }
        
        Arrays.sort(arr);
        
        int left = 0, right = N-1;
        long sum = 0;
        if(left == 0 && right == 0) {
        	sum= arr[0];
        	System.out.println(sum);
        	return ;
        }
        if(N%2 == 1) {
        	sum = Math.max(sum, arr[N-1]);
        	right -= 1;
        }
        
        while(left < right) {
        	sum = Math.max(sum, arr[left] + arr[right]);
        	left++;
        	right--;
        }
        
        System.out.println(sum);
        
    }
    
}