백준(BOJ) 7344 나무 막대(Python)

 

 

문제 내용

 

 

간단한 그리디 문제.

문제를 풀기 위한 아이디어를 떠올리기 쉬웠던, 문제에 나온 대로만 하면 되는 문제였다.

입력받은 막대의 l, w 값을 l의 오름차순에 w의 오름차순으로 정렬하고, [[[0,0]]] 형태의 리스트를 만든다. 이 리스트를 L이라 하자. L은 가동되는 기계가 어떤 막대를 가공할 지를 담고 있을 것이다. L의 최종 개수는 기계의 개수이고, 이는 최소 작동 준비 시간일 것이다.

우리는 각 막대의 l, w 값을 L의 모든 원소의 마지막 원소의 0, 1번째 인덱스에 위치한 값과 비교할 것이다.

그리고 l<=0번째 인덱스의 값, w<=1번째 인덱스의 값을 모두 만족하면 그 원소에 [l,w]를 추가할 것이다.

풀어서 설명하니 복잡해 보이는데, 코드를 보는 것이 이해가 빠를 것이라고 생각한다.

 

코드는 다음과 같다.

 

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

t=int(input())
for i in range(t):
    n=int(input())
    L1=list(map(int,input().split()))
    L2=[[L1[j],L1[j+1]] for j in range(0,n*2,2)]
    L2.sort()
    L2=deque(L2)
    L3=[[[0,0]]]
    for j in range(n):
        X=L2.popleft()
        flag=0
        for k in range(len(L3)):
            if X[0]>=L3[k][-1][0] and X[1]>=L3[k][-1][1]:
                L3[k].append(X)
                flag=1
                break
        if not flag:
            L3.append([X])
    print(len(L3))

 

풀고 난 느낌은, 문제가 overrated된 것 같다는 생각이다.

아무리 생각해도 골드2 수준의 문제는 아닌 것 같다.