99클럽 코테 스터디 9일차 TIL - 백준 2437번 : 저울

✅ 문제

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

• N개의 저울추가 주어질 때, 이 추들을 사용해 측정할 수 없는 양의 정수 무게 중 최소값을 구하기.
• 한쪽은 물체, 다른 한쪽은 추를 놓을 수 있다. 즉, 연속적인 N개의 추들로 물체의 무게를 표현하는 저울이다.
• 예) 저울추 3, 1, 6, 2, 7, 30, 1인 경우, 측정할 수 없는 가장 작은 양의 정수 무게는 21

✅ 분류

• 그리디 알고리즘
• 정렬 (오름차순)

✅ 공부한 내용

- 풀이 로직

1. 추들을 오름차순으로 정렬
2. sum 변수를 사용해서 현재까지 추들로 만들 수 있는 연속된 무게의 최댓값 변수 저장.
3. 각 추를 순서대로 확인
   1. 현재 추의 무게가 sum+1보다 크다면, sum+1은 만들 수 없는 최소 무게 (정답)
   2. 그렇지 않다면, 추를 사용하면 범위를 sum + arr[i]까지 더할 수 있다.
4. 모든 추를 다 사용했다면, 측정할 수 없는 가장 작은 양의 정수 무게 sum+1 출력

✅ 회고

그리디 알고리즘을 보고 금방 코드는 금방 구현했으나, 아직 TIL을 작성할 때 글로 풀어내는 능력이 부족해 다른 분들 풀이와 설명도 읽어보고 참고한다.

문제를 꾸준히 자주 풀고, 기록하는 습관을 더 길러야겠다.

 

🔑 풀이

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr); // 오름차순 정렬

        int sum = 0;
        for (int i = 0; i < N; i++) {
            if (arr[i] > sum + 1) {
                break; // 더 이상 연속된 무게를 만들 수 없음
            }
            sum += arr[i];
        }
        System.out.println(sum + 1);
    }
}

 

참고

https://codingfood.tistory.com/14