백준 11000, 2457 문제 풀이 (Feat. 그리디 & 파이썬)

백준 11000번 강의실 배정

문제 설명

N개의 강의 중 i번째 강의가 si시간에 시작해 ti에 끝이난다. 최소의 강의실을 사용하여 모든 강의를 배정하는 방법을 구하는 문제입니다.

 

문제 풀이

모든 강의를 배정할 수 있는 최소 강의실 개수를 구하는 문제이므로 언제 강의실의 개수가 늘어나는지를 살펴보면됩니다.

i번째 강의를 배정할 때 강의실의 개수가 늘어나는 경우는, 현재까지 생겨난 강의실의 마지막 강의가 끝나는 시간이 i 강의의 시작 시간보다  모두 늦은 경우입니다.

 

기존 강의실에 배정할 수 있는 경우

기존 강의실에 배정할 경우

새로운 강의 C의 시작시간 S3가 두 강의실의 마지막 강의가 끝나는 시간 T1, T2 중 T1보다 크므로 강의실 1에 강의 A가 끝난 뒤 배정하면 됩니다.

 

 

새로운 강의실을 배정해야 하는 경우

새로운 강의실을 배정해야 하는 경우

새로운 강의 C의 시작시간 S3가 두 강의실의 마지막 강의가 끝나는 시간 T1, T2보다 작으므로 새로운 강의실 3이 필요합니다.

 

이처럼 현재까지 추가된 강의실들의 마지막 강의가 끝난 시간 중 현재 추가해야할 강의의 시작시간보다 작은 강의가 있는 경우 기존 강의실에 배정 가능합니다. 이 말은 추가된 강의실들의 마지막 강의의 끝나는 시간 중 가장 빨리 끝나는 시간(위의 예시에서는 T1)이 현재 추가할 강의의 시작 시간(위의 예시에서는 S3)보다 작은 경우 기존 강의실에 배정할 수 있습니다. -> 새로운 강의실을 추가하지 않습니다.

 

반대로 강의실들의 마지막 강의의 끝나는 시간 중 가장 빨리 끝나는 시간이 현재 추가할 강의의 시작 시간보다 클 경우 새로운 강의실을 추가해줘야합니다.

 

그러므로 현재까지 강의실에 배정된 강의들의 끝나는 시간을 정렬된 형태로 저장할 수 있는 자료구조가 필요합니다. -> 최소 힙

 

강의실을 배정하는 순서 결정 방법 -> 강의의 시작 시간을 기준으로 새로운 강의실을 배정해야 하는지 결정했었으므로 강의의 시작 시간이 강의실 배정 순서가 됩니다.

 

코드

from heapq import heappush, heappop


N = int(input())
lectures = [list(map(int, input().split())) for _ in range(N)]
lectures.sort()
classRoom = []
heappush(classRoom, lectures[0][1])

for i in range(1, N):
    if classRoom[0] <= lectures[i][0]:
        heappop(classRoom)
    heappush(classRoom, lectures[i][1])

print(len(classRoom))

 

입력받은 강의를 강의 시작 시간을 기준으로 오름차순 정렬합니다.

classRoom 변수에 현재까지 강의실에 배정된 강의들의 끝나는 시간을 저장합니다.

일찍 시작하는 강의부터 반복문을 통해 새로운 강의실의 추가 여부를 결정합니다.

현재까지 강의실에 배정된 강의들의 끝나는 시간이 현재 추가하려는 강의의 시작시간보다 작거나 같다면 기존 강의실에 추가할 수 있다는 뜻입니다. 그러므로 해당 강의실의 마지막 강의 시간을 현재 강의의 끝나는 시간으로 변경해줍니다.

만약 강의실에 배정된 강의들의 끝나는 시간이 현재 추가하려는 강의의 시작시간보다 크다면 새로운 강의실을 추가해야된다는 뜻입니다. 그러므로 해당 강의의 끝나는 시간을 새롭게 heappush 해줍니다.

 

 

백준 2457번 공주님의 정원

꽃이 피고 지는 기간이 주어지고 3월 1일부터 11월 30일까지 매일 한가지 꽃이 피어있도록 하는 최소 꽃의 종류 개수를 구하는 문제입니다.

 

최소한의 꽃개수로 3월 1일부터 11월 30일까지 무조건 하루에 한가지 꽃이 살아있도록 해야합니다.

여기서 최소의 꽃 개수를 구해야하므로 잘 생각해보면 꽃이 피어 있는 기간이 겹치는 꽃은 두 개 밖에 없다(?)는 것을 알 수 있습니다.

기간이 겹치는 꽃이 3개일 경우

기간이 겹치는 꽃은 두 개 밖에 없다는 뜻은 다음과 같습니다.

위의 꽃들이 겹치는 기간 P에 꽃 A, B, C 세 개가 겹쳐있는 경우를 살펴보겠습니다. 위와 같은 경우는 최소의 꽃 개수가 아닙니다.

그 이유는 꽃 A와 꽃 C가 P기간이 겹치므로 꽃B가 없이도 빈 기간이 생기지 않기 때문입니다.

 

그러므로 다음과 같이 기간이 겹치는 꽃은 두 개 밖에 생기지 않는다는 것을 알 수 있습니다.

기간이 겹치는 꽃은 2개

 

기간이 겹치는 꽃이 두개라는 것은 겹치는 기간을 가진 꽃 중 가장 늦게 지는 꽃을 골라 나가는 것이 꽃의 종류 개수를 줄이는데 도움이 된다는 것을 알 수 있습니다. (꽃이 지는 기간을 이어나가기 위해서는 기간이 겹치는 꽃이 2개를 넘어갈 수 있습니다.)

 

꽃A가 이미 선택되었다고 가정했을 때 다음 꽃을 고르는 과정을 살펴보도록 하겠습니다.

꽃 A 이후 기간이 비지 않게 다음 꽃을 고르는 방법은 꽃 B,C,D 중 하나를 고르는 것입니다. 위서 살펴본 대로 최소 꽃 개수를 구하는 방법은 기간이 겹치는 꽃이 2개를 넘어서면 안됩니다. 그러므로 꽃 B를 선택할 경우 꽃 D를 다음 꽃으로 선택해야 하므로 기간이 겹치는 꽃이 3개이므로 꽃 B는 선택하지 않습니다. 그 다음 꽃 C와 D 중 꽃 C가 더 늦게 지므로 꽃 C를 선택하고, 꽃 D, E를 선택하면 기한 내에 꽃을 계속 피울 수 있습니다.

 

코드

from heapq import heappush, heappop

N = int(input())
flowers = []

for _ in range(N):
    sm, sd, em, ed = list(map(int, input().split()))
    flowers.append([sm*100+sd, em*100+ed])
flowers.sort()

selected = []
si = 0
now = 301
answer = 0

while now <= 1130:
    for i in range(si, N):
        if flowers[i][0] <= now < flowers[i][1]:
            heappush(selected, -flowers[i][1])
            si = i+1
        elif flowers[i][0] > now:
            break

    if selected:
        now = -heappop(selected)
        answer += 1
        selected = []
    else:
        break
if now > 1130:
    print(answer)
else:
    print(0)

 

날짜를 비교하는 방법은 현재 월 * 100 + 현재 일 로 비교했습니다.

입력받은 날짜를 꽃이 피기 시작하는 날을 기준으로 오름차순으로 정렬했습니다.

현재 꽃의 피고 지는 날짜 사이에 선택된 꽃이 지는 날이 있다면 두 꽃은 겹치는 기간이 존재하므로 기간을 이어나갈 꽃으로 선정될 수 있습니다. 현재 선정될 수 있는 꽃들 중 가장 늦게 지는 꽃을 선택해줍니다.

기간을 이어나갈 수 있는 꽃이 지는 마지막 날짜가 1130보다 크다면 성공입니다.

 

 

 

정리

그리디 알고리즘은 현재 상황에서 최선의 선택을 해야한다는 것입니다.

첫 번째 문제는 기존 강의실에 현재 강의를 편성할 수 있다면, 현재 강의실들 중 가장 마지막에 끝나는 강의의 종료 시간이 가장 낮은 것에 현재 강의를 편성하는 것이 최선의 선택이 될 것입니다.

두 번째 문제는 결정된 꽃과 기간이 겹치는 것 중 가장 늦게 지는 꽃을 선정하는 것이 최선의 선택이 될 것입니다.

이와 같이 이미 결정된 것들을 기반으로 최선의 선택을 하도록 로직을 구성하는 것이 중요합니다.