[자바]백준 2437번 저울 [그리디][엄탱]

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

 

그리디 알고리즘이란!?

Greedy는 ‘탐욕스러운, 욕심 많은’ 이란 뜻이다.
탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.

 

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

2437번: 저울

문제 설명

다른거 필요없이, 한문장으로 설명이 가능하다.

주어진 무게추들로 만들 수 없는 무게의 최솟값을 구하면 된다.

해설

해당 문제는 알고리즘 분류를 보면 정렬도 포함되어 있는데 구할 수 없는 무게 최솟값을 알아보기 위해 오름참순으로 정렬을 해줘야한다.

 

이 문제의 핵심은 아래와 같다.

• 1, 2, 3의 무게를 구할 수 있다고 가정해보자.
• 그럼 4의 무게를 구할 수 있는지 알아보자.
• 다음으로 꺼낸 추의 무게가 3이라고 가정하자.
• 꺼낸 3으로 조합할 수 있는 무게는 1, 2, 3(기존 무게)와 4, 5, 6(기존 무게와 3을 합친 무게들) 이 있다.
• 그럼 4(기존에 알아볼려던 숫자) + 3(꺼낸 무게)가 다음 알아볼 숫자가 된다.

 

• 이번엔 꺼낸 추의 무게가 3이 아니라 5라고 가정하자
• 5로 조합할 수 있는건 1, 2, 3, 5, 6, 7, 8 인것이다. 
• 그러면 구할 수 없는 무게의 최솟값은 4인것이다.

 

 

그리디의 핵심은 당장 눈앞의 상황을 해결하고 다음으로 나아가는 것이다.

어떤 상황을 해결해야할까?

위의 방법을 토대로 가장 최솟값 1부터 확인을 해보는 것이다.

 

import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int[] arr = new int[T];
        
        for (int i = 0; i < T; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(arr);
        
        // 여기서부터 그리디 알고리즘
        int min = 1;
        
        for (int num: arr) {
            if (min < num) {
                break;
            }
            min += num;
        } 
        
        bw.write(min + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

기타

그리디문제는 유형이 다양한것 같다.

이 문제 유형은 이제 풀 수 있어 하면 다른 문제 유형이 나와 당혹스럽게 만든다.

 

이 문제도 방법만 안다면 코드자체는 엄청 짧아 쉽게 느껴진다.

하지만 방법을 유추하는게 생각보다 쉽지 않은것 같다.