그리디 알고리즘 - 백준 1931 python

그리디 알고리즘이란

동적 프로그래밍에서 지나치게 많은 일을 한다는 점을 착안하여 고안된 알고리즘으로

특정 상황에서 최적해를 구하는데 사용합니다.

 

특정 상황이라는 점이 키포인트이며 이를 만족하지 못하면 효과적인 알고리즘이 아닐 수 있습니다.

 

바로 문제부터 풀어보시죠

 

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

1931번: 회의실 배정

가능한 많은 회의실을 이용하는 문제였는데

회의 시간이 같거나 같은 시간에 시작해서 다르게 끝나는 경우가 많은 문제였습니다.

import sys
input = sys.stdin.readline
n = int(input().rstrip())
cases = [list(map(int,input().rstrip().split())) for _ in range(n)]
cases.sort(key= lambda x : -x[0])
d = [0] * (n+1)
cur = [cases[0]]
for i in range(n) :
    if cur[-1][0] > cases[i][1] :
        cur.append(cases[i])
print(len(cur))

처음에 제출한 답안인데 제일 늦게 하는 회의는 무조건 포함해야하므로

회의 시간을 늦은 순서부터 정렬했습니다 

그러나 위 코드는 회의 시간이 같거나 시작시간이 같은데 다르게 끝나는 회의들 사이에서 최적의 선택을 하는데

어려움이 있었습니다.

 

import sys
n = int(input().rstrip())
cases = [list(map(int,input().rstrip().split())) for _ in range(n)]
cases.sort(key= lambda x : (x[0],x[1]))
d = [0] *n
cur = 0
for i in range(0,n) :
    if i == 0 :
        d[0] = 1
        cur = cases[0][1]
        continue
    if cases[i][0] >= cur :
        d[i] = d[i-1] + 1
        cur = cases[i][1]
    else :
        d[i] = d[i-1]
        cur = min(cur,cases[i][1])
print(d[-1])

그래서 이를 해결하기 위해 시작시간을 기준으로 정렬하고 두 번째 조건으로 회의시간이 빨리 끝나는 순서대로 정렬했습니다.

이렇게 정렬하면 같은 시간에 시작하고 같은 시간에 끝나는 회의를 포함할 수 있습니다.

 

i가 0일때는 가장 일찍 시작하는 회의이므로 포함시켜줍니다.

그리고 시작시간이 cur의 끝나는 시간보다 크거나 같다면 d배열에서 갯수를 1개 늘려주고 cur값을 바꿔줍니다.

아니라면 d의 값은 이전 값을 가져오고 cur값은 현재 cur값과 대상cases의 끝나는 시간 중에 더욱 작은 수를 선택해줍니다

이렇게하면 끝나는 시간이 짧은 회의를 선택할 수 있게 됩니다.