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

오늘의 학습 키워드

• 그리디
• 정렬
• 누적합
• 최소값 탐색

---

공부한 내용 정리

이 문제는 무게추를 이용해 만들 수 없는 가장 작은 무게를 찾는 문제다.
핵심 아이디어는 오름차순으로 정렬한 후, 1부터 차례로 누적하며 비교하는 것이다..

처음 target을 1로 시작해서, 지금까지 만들 수 있는 무게 범위는 [1, target)이다.
만약 다음 무게추가 target보다 작거나 같으면 target을 확장할 수 있고,
반대로 크다면 그 순간 target은 만들 수 없는 가장 작은 무게가 된다.

예를 들어 [1, 1, 2, 3, 6, 7, 30] 같은 배열을 보면,
target이 누적되다가 30 앞에서 멈춰버리게 되고, 그 시점의 target이 정답이 되는 구조다.

---

소스코드

/*
저울
입력 : N 무게추 갯수 N <= 1000
      N개 각 무게추의 무게
로직 : 무게추 배열을 오름차순 정령
      반복문으로 1부터 비교,
      만약 찾는 무게가 추 보다 작으면 타겟에 추무게 추가
      아니면 그 무게는 찾을 수 없음.
출력 : 측정할수 없는 무게 중 최소 값
*/

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

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());
    // 무게 추 무게
    String[] input = br.readLine().split(" ");
    int[] weights = new int[N];
    for (int i = 0; i < N; i++) {
      // 문자 > int 변환
      weights[i] = Integer.parseInt(input[i]);
    }
    
    // ----로직
    // 1. 무 추게 정렬
    Arrays.sort(weights);
    // 2. 반복문 으로 비교
    int target = 1;
    for (int i = 0; i < N; i++) {
      if (weights[i] <= target)
        target += weights[i];
      else
        break;
    }
    System.out.println(target);

  }
}

---

오늘의 회고

• 어떤 문제가 있었고, 나는 어떤 시도를 했는지

처음에는 모든 조합을 구해서 비교하려 했지만, 시간 복잡도가 너무 컷다. 그래서 그리디하게 접근하는 방식으로 바꿔보았다.

 

• 어떻게 해결했는지

무게추 배열을 오름차순 정렬하고, 누적 가능한 범위를 target 변수로 유지하면서 문제 조건에 따라 target을 증가시켰다.

 

• 무엇을 새롭게 알았는지

"1부터 만들 수 있는 무게를 채워간다"는 접근은 많은 그리디 문제에서 사용된다는 걸 느꼈고,
오름차순 정렬 후 가능한 범위를 누적하는 패턴이 유용하다는 걸 배웠다.

골드 2단계 문제여서 솔직히 조금 쫄았는데 의외로 할만한데? 라는 생각이 들게 해준 문제인 것 같다.

 

• 내일 학습할 것은 무엇인지

내일은 우선순위 큐(PriorityQueue)를 사용하는 문제나, BFS/DFS 탐색 문제에 도전해보려고 한다.

---