[Unsolved][JAVA] 백준 14575 뒤풀이

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

 

 

1. 서론

 

이분탐색 문제이다. 그런데 이제 푸는 법을 모르겠는... 범위가 n개 주어지는데 그 범위 안에 만족하는 값 x가 다 같은 값이 아니라 그냥 x이하면 되는 걸 처리하는 게 생각이 안 나서 결국 혼자 해결하지 못해 버렸다... ㅜㅜ

 

2. 문제 풀이

 

사람수 n, 사람에게 줘야하는 술의 수의 합 t가 있다.

그리고 그 사람 별로 소화 가능한 술의 범위가 있다.

 

문제의 조건은 이거다.

 

1) 이 범위를 모두 만족시켜야 함.

2) 그 값은 모두 같은 값이 아님, 사람마다 다르게 줄 수 있음 범위 안에서

 

각자 사람들에게 각자 다른 양의 술을 주지만, 그 합은 t여야 하고, 그 값을 초과하지 않는 값 중에서 최솟값을 구하는 문제이다.

 

처음에는 그냥 while문 안에서 n번 돌면 시간 초과가 날 것 같아서 꼼수를 써서 조건문을 만들었는데 당연히 조건을 충족시키지 못하고 틀렸다.

 

n번 반복문을 도는 것이 정답인데 그 안에서 어떤 조건으로 나눠서 값을 구해야 하는지 갈피가 잡히지 않았다.

일일이 사람마다 x~y값을 체크하더라도 우리가 구하는 값은 그 모든 범위를 충족하는 단 하나의 값이 아니라 어떤 특정한 값 이하는 다 허용되는 문제이기 때문이다.

 

결국 구글링을 돌렸고, 이 블로그를 참조했다.

https://onfonf.tistory.com/72

[백준 / Java] 14575. 뒤풀이

 

lower, upper로 범위를 만든다.

lower는 저 범위들을 돌면서 최저값, 즉 범위 중에 가장 작은 값들의 합이다.

upper는 범위들의 최대값이나 mid값 중 작은 값들의 합이다.

 

이 양쪽의 합 범위 안에 t가 들어가면 ans의 값을 경신한다. (최솟값으로)

위의 링크에서는 매번 Math.min으로 최솟값을 찾아 돌려줬지만 그냥 해당 상황에 해당될 때마다 ans 값을 경신해 줘도 맞았다.

아마도 이동하면서 가장 마지막에 만나는 값이 최솟값이 되는듯 하다.

 

 

반응형

 

 

 

3. 코드 설명

 

import java.io.*;
import java.util.*;
import java.awt.Point;

public class Main {

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int n = Integer.parseInt(st.nextToken());
    int t = Integer.parseInt(st.nextToken());

    Point[] list = new Point[n];
    long l = Integer.MAX_VALUE, r = 0;
    for (int i = 0; i < n; i++) {
      st = new StringTokenizer(br.readLine());
      int x = Integer.parseInt(st.nextToken());
      int y = Integer.parseInt(st.nextToken());
      list[i] = new Point(x, y);
      if (l > x) //범위 중 가장 최솟값 정하기
        l = x;
      if (r < y) //범위 중 가장 최댓값 정하기
        r = y;
    }

    long ans = Integer.MAX_VALUE;
    while (l <= r) {
      long mid = l + (r - l) / 2;

      int upper = 0, lower = 0, f = 0;
      for (int i = 0; i < n; i++) {
       Point p = list[i];
       if (p.x > mid) {mid가 최솟값보다도 작으면 그냥 바로 범위를 옮겨버린다
         l = mid + 1;
         f = 1;
         break;
       }
       lower += p.x; //최솟값의 합
       upper += Math.min(mid, p.y); //최대값의 합
      }

      if (f == 0) {
        if (lower <= t && upper >= t) { //총 합이 두 범위 안에 드는경우(답인 경우)
          ans = mid;
          r = mid - 1; //더 작은 경우를 찾기 위해 범위를 줄임
        }
        else if (lower > t)
          r = mid - 1; // lower값이 너무 크기 때문에 범위를 줄임
        else
          l = mid + 1; // 범위를 늘림
      }
    }

    if (ans == Integer.MAX_VALUE) //답이 없기 때문에 -1
      ans = -1;

    System.out.print(ans);
  }
}

 

 

주석 참조@@

최솟값을 구하는 것이 답이기 때문에 계속 더 작은 범위로 이동하기 때문에 Math.min 갱신 없이 최솟값을 저장할 수 있는 것이다!!