•
풀이 방법
처음엔 감이 안잡혀 그림으로 그리며 방법을 찾았다.
■, □ 문자를 사용하여 빈 시간 & 사용시간을 표현하여 전체 사용 여부를 한눈에 파악할 수 있었다.
아래에 그림도 출력되는 코드를 남겼으니, 참고하면 좋을 듯 하다.
1.
그리디 알고리즘은 현재 상황에서 가장 좋은 상황을 구하는 문제이다.
그렇다면 시작시간이 빠른 순서대로 정렬을 한 후, 그 순서를 따라가면 편하다.
이때 끝나는 시간도 정렬해야 더욱 편하다.
2.
조건을 잘 확인한다. 시작 시간과 끝나는 시간이 동일한지, 일찍 시작하더라도 굉장히 많은 시간이 할당된 회의인지 확인한 후 조절해준다.
•
성공 코드
•
코드 설명
회의실 사용정보를 입력받은 후, 시작 시간 정렬 → 끝나는 시간 정렬을 사용하여 경우를 구하기 편하게 만들었다.
회의는 무조건 1번은 진행하기 때문에 count의 기본값은 1 이다
N = int(input())
rooms = []
count = 1 # 무조건 회의 1번은 한다.
for _ in range(N):
room = tuple(map(int, input().split()))
rooms.append(room)
# 시작시간 정렬 후, 끝나는 시간 다시 정렬
rooms.sort(key=lambda x:x[0])
rooms.sort(key=lambda x:x[1])
...
Python
복사
맨 처음 사용되는 회의 시간부터 확인하였다.
그 이후, 모든 사용시간에 대해 조회한다.
...
# 가장 처음 가져옴
before = rooms.pop(0)
for room in rooms:
...
Python
복사
시작시간과 끝나는 시간이 같을 때는 시작과 동시에 끝나기 때문에 동시에 다른 회의를 할 수 있다. (문제 설명에 나와있음)
조건에 맞을 경우 회의실 사용 횟수 +1
...
for room in rooms:
# 시작시간과 끝나는 시간이 동일
if room[0] == room[1]:
count += 1
continue
...
Python
복사
이 부분이 핵심인데, 이전에 빨리 회의가 시작하더라도 더 늦게 시작하는 회의보다 늦게 끝나는 경우가 있다.
만약 위와 같은 상황에서, 그 사이의 시간만을 사용하는 회의가 이후에 존재한다면 최대한 많은 경우의 수를 구해야되는 문제에 오답이 생긴다.
회의실의 시작시간은 0부터이다. 문제 설명에도 아래와 같이 나와있다.
시작 시간과 끝나는 시간은 보다 작거나 같은 자연수 또는 0이다.
EX)
- (1,10)일 때, 시작시간은 1 / 끝나는 시간은 10이라고 하자
- 사용하지 않는 시간은 □ 로, 사용하는 시간은 ■ 로 표시할 때 아래와 같다.
□ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■
- 이 상황에서 일찍 시작한 회의가, 나중에 시작하는 회의들보다 늦게 끝나는 경우이다.
- (1,10) / (2,4)
□ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■
□ □ ■ ■ ■ □ □ □ □ □ □
- 4 ~ 10의 공간을 사용하는 회의가 이후에 나온다면, 반례가 생기는 것이다.
- (1,10) / (2,4) / ... / (5,7) / ...
□ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■
□ □ ■ ■ ■
...
□ □ □ □ □ ■ ■ ■ □ □ □
...
Plain Text
복사
...
for room in rooms:
...
# 더 좁은 범위(시작 시간이 더 늦고, 끝나는 시간은 더 빠른 회의)의 회의가 존재할 때 변경
elif before[0] < room[1] and before[1] > room[1]:
before = room
continue
...
Python
복사
만약 회의 시간이 겹치지 않는 경우에는 그냥 추가해준다.
이후 for문이 끝나면 총 사용가능 횟수를 출력하며 끝난다.
...
for room in rooms:
...
# 회의가 겹치지 않을 때
elif not before[1] > room[0]:
before = room
count += 1
print(count)
Python
복사
그림 출력되는 코드
예시 출력 결과