[백준 - 7344번] 나무 막대 - Java

문제 링크

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

문제

티어: 골드 2
알고리즘: 그리디, 정렬

입력

첫째 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 데이터는 두 줄에 걸쳐 주어집니다. 첫째 줄에는 나무 막대의 개수 n (1 ≤ n ≤ 5000) 이 주어지고, 다음 줄에 l1, w1, l2, w2, ... ,ln, wn (각 막대의 길이와 무게를 뜻하고, 10000을 넘지 않는 정수입니다) 가 공백을 두고 차례로 주어집니다.

출력

각 테스트 케이스별로 필요한 최소 작동 준비 시간을 한 줄에 걸쳐 출력합니다.

풀이

작동 준비 시간을 최소로 하는게 목표다.

그럴려면 최대한 도구를 바꾸지 않고 가공을 해야 한다.

일단 l<=l'를 만족시키는 최선의 선택을 하려면 당연히 l을 기준으로 오름차순으로 정렬해야 한다.

그런데 두 번째 조건 w<=w'도 만족시켜야 한다. l만 기준으로 정렬하면 w는 상관 없을까?
상관 없다. l은 작지만 w가 큰 것을 선택해서 다음번 가공할 막대가 없다면, 어차피 준비 시간이 1분 필요하게 된다. 그러니까 w는 상관 없다는 얘기다.

그러면 다음 막대가 w조건을 만족하지 않는다면 어떻게 해야할까? 그 다음 막대로 넘어가 가공할 수 있는지를 검사하면 된다. 이를 마지막 막대기까지 체크한다.

이렇게 하는 이유는 막대를 준비 시간 없이 최대한 가공하면서, l과 w가 작은 막대를 최대한 남겨두기 때문에 최적의 해를 구할 수 있게 된다. (만약 w가 만족하지 않는다고 바로 그 막대를 가공한다면, 이러한 가능성을 다 없앤다.)

예를 들어 다음과 같이 6개의 막대가 있을 때
6
1 10
2 3
3 11
4 12
5 4
6 5

1분 -> (1,10) 1분 -> (2,3) -> (3,11) -> (4,12) 1분 -> (5,4) -> (6,5)으로 총 3분이지만,

1분 -> (1,10) -> (3,11) -> (4,12) 1분 -> (2,3) -> (5,4) -> (6,5)로 총 2분이 걸린다.

그리디 + 정렬 풀이의 시간 복잡도는 O(N^2)이다.

소스 코드

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

class Stick implements Comparable<Stick> {
    int l, w;
    Stick(int l, int w) {
        this.l = l;
        this.w = w;
    }
    
    @Override
    public int compareTo(Stick o) {
        if(this.l < o.l) {
            return -1;
        } else if(this.l > o.l) {
            return 1;
        }
        return 0;
    }
}

public class Main {
    static int T;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      T = Integer.parseInt(br.readLine());
      StringBuilder sb = new StringBuilder();
      for(int k=0; k<T; k++) {
          int N = Integer.parseInt(br.readLine());
          Stick[] sticks = new Stick[N];
          boolean[] visited = new boolean[N];
          StringTokenizer st = new StringTokenizer(br.readLine());
          for(int i=0; i<N; i++) {
              sticks[i] = new Stick(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
          }
          Arrays.sort(sticks);
          int time = 0;
          for(int i=0; i<N; i++) {
              if(!visited[i]) {
                  visited[i] = true;
                  time += 1;
                  int bInd = i;
                  for(int j=i + 1; j<N; j++) {
                      if(!visited[j] && sticks[bInd].w <= sticks[j].w) {
                          visited[j] = true;
                          bInd = j;
                      }
                  }
              }
          }
          sb.append(time).append("\n");
      }
      System.out.println(sb.toString().trim());
  }
}