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번은 왜?

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가 인자에 있어야겠네
▼
그렇게 해서 작성한게 이 코드

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

참고 레퍼런스

메모

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

풀이 키워드​

풀이 코드​

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

풀이 해설​

왜 이 코드는 틀림?​

참고 레퍼런스​

메모​