99클럽 코테 스터디 24일차 TIL (챌린저): [백준][Java] 2437 저울 - 골드2

 

문제 보기

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

 

 

풀이

그리디를 사용해 문제를 풀었다.

 

int num = 0;
while (true) {
  num++;

  int sum = 0;
  for(int j = N - 1; j >= 0; j--) {
    if(num - sum >= arr[j]) {
      sum += arr[j];
    }
    if(sum == num) {
      break;
    }
  }
  if(sum != num) {
    bw.write(num + "\n");
    break;
  }
}

arr은 정렬 된 추 배열이다.

 

그냥 1부터 더해가며 이 수를 계산할 수 있는지 검토해 보았다.

큰 수 부터 내려가며 num - sum보다 작을 경우 sum에 더해 주고 만약 sum과 num이 같아 졌을 경우 반복문을 빠져나왔다.

만약 for문이 끝났는데도 sum이 num이 되지 않았을 경우 정답이 된다.

 

큰 수 부터 더하는 이유는, 그 수 보다 작은 수들은 더해서 만들 수 있다고 결론이 난 상태라 그렇다.

예를 들어 11을 만든다면, 이미 11 검증까지 온 것 자체가 7을 빼더라도 그 앞 수들을 만들 수 있다는 결론이 난 상태이다.

 

사실 시간 초과가 날 것 같았는데 나지 않아서 의아하다.

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
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 IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());
    int[] arr = new int[N];
    for(int i = 0; i < N; i++) {
      arr[i] = Integer.parseInt(st.nextToken());
    }
    Arrays.sort(arr);

    int num = 0;
    while (true) {
      num++;

      int sum = 0;
      for(int j = N - 1; j >= 0; j--) {
        if(num - sum >= arr[j]) {
          sum += arr[j];
        }
        if(sum == num) {
          break;
        }
      }
      if(sum != num) {
        bw.write(num + "\n");
        break;
      }
    }


    bw.flush();
    bw.close();
  }

}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Gold/2437.%E2%80%85%EC%A0%80%EC%9A%B8

CodingTest_AutoSave/백준/Gold/2437. 저울 at main · MetroDefro/CodingTest_AutoSave