본문으로 건너뛰기

1931 - 회의실 배정

info
  • 문제 보기: 1931 - 회의실 배정
  • 소요 시간: 💥1시간 초과
  • 풀이 언어: python
  • 체감 난이도: 3️⃣~4️⃣
  • 리뷰 횟수: ✅

풀이 키워드​

스포주의

그리디

I HATE GREEDY

풀이 코드​

info
  • 메모리: 51900 KB
  • 시간: 200 ms
import sys
input = sys.stdin.readline

def solution():
    n = int(input())
    data = []
    for _ in range(n):
        s, t = map(int, input().split())
        data.append((s, t))
    
    # 끝 시간 - 시작 시간 순 정렬
    # ex) 4 4 / 1 4 이렇게 입력되면 1 4 / 4 4 로 정렬하도록
    data.sort(key=lambda x: (x[1], x[0]))
    
    ans = 1
    st = data[0][1] # start time
    for i in range(1, n):
        if st <= data[i][0]:
            st = data[i][1]
            ans += 1
            
    print(ans)


if __name__ == '__main__':
    solution()

다빈치코딩 알고리즘에서 단계별로 잘 설명해놓음.

기본적인 발상은 이러하다.

  1. (⭐중요⭐) 최대한 남은 시간을 많이 확보하면서 회의를 선택하는 것이 유리하다.
  2. 종료 시간이 같은 회의 중에서는 시작 시간이 가장 빠른 순으로 선택해야 한다.

그래서 1과 2를 코드로 옮기자면, 입력 데이터를 끝나는 시간 - 시작 시간 순으로 오름차순 정렬해야 한다.


1번은 알겠는데, 2번은 왜?​

2번은 이 문제의 특수성 때문이다.

하단의 케이스를 생각해보자.

# 입력
2
4 4
1 4

문제에 쓰인대로 회의는 시작하자마자 끝날 수 있기 때문에, 답은 (1, 4) --> (4, 4) 를 고른 2가 되어야 한다.

하지만 2번대로 시작 시간 순 정렬을 하지 않는다면, 로직은 (4, 4) 회의만을 선택한 채 종료되어 1을 출력할 것이다.


풀이 해설​

왜 이 코드는 틀림?​

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = 0
data = []
memo = dict()

# i번째 회의를 선택하거나 하지 않을 때 가지는 최대 회의 수
# prev: i 이전에 선택했던 회의
def dp(prev, i):
    global memo
    
    if i > n:
        return 0
    
    if (prev, i) in memo:
        return memo[(prev, i)]
        
    a, b = 0, 0
    # i 선택시
    
    if data[i][0] >= data[prev][1]:
        a = dp(i, i+1) + 1 # +1 for counting self
    b = dp(prev, i+1)
        
    mx = max(a, b)
    memo[(prev, i)] = mx
    return mx

def solution():
    global n, data
    n = int(input())
    data.append([0, 0]) # initial prev
    for _ in range(n):
        data.append(list(map(int, input().split())))
    
    data.sort()
    print(dp(0, 1))


if __name__ == '__main__':
    solution()

처음 풀었을땐 1시간 1분쯤 되어서 그럴싸한 DP 발상이 됨

dp(i, selected) 같은 i가 선택됐냐(True)/안됐냐(False)의 기준으로 DP state를 나눠보려 했는데 뭔가 안돼서 머리 굴려봄
▼
i 선택 안하면 마지막 회의 끝난 시간 어캐 알건데?
▼
아 그럼 prev가 인자에 있어야겠네
▼
그렇게 해서 작성한게 이 코드


채점 결과는 메모리 초과였지만 정해를 보기 전에 이 발상을 살려보고 싶어서 이것저것 레퍼런스를 읽어봤다.


참고 레퍼런스​

  1. Memoization & DP table
  2. 파이썬의 내장 캐싱 데코레이터
  3. 수학적으로 잘 설명한듯

메모​

  • 백준에서 채점해본 (발품 팔아본) 결과, 재귀 깊이 10**5 ~ 10**6 사이 언저리에서 128 MB 정도 잡아먹는듯 하다.
    • 왜냐하면 limit을 10**5으로 잡으면 RTE(Recursion Error)가 터지고, 10**6으로 잡으면 메모리 초과가 뜨기 때문
  • 앞으로 메모리제한이 128 MB면 그리디를 의심하거나 bottom-up 으로 DP를 작성하는 것이 좋아보인다.
    • 실전에선 그리디일 가능성이 높지만, 정 못 풀겠으면 최후의 보루로 DP를 시도라도 해봐야 하니까...