백준 알고리즘의 그리디 파트, 1931번 회의실배정 문제를 파이썬코드와 함께 내가 이해한대로 설명해보려 한다.
문제 출처
https://www.acmicpc.net/problem/1931
1931번: 회의실배정
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
www.acmicpc.net
먼저 그리디라는 알고리즘은 그냥 당장 단순하게 좋은것만 생각하는 알고리즘이다.
따라서 이후의 상황은 그냥 고려하지 않는 알고리즘이다.
문제를 잘 읽어 보고, 그리디를 써야겠다는 생각이 들 때 까지 익숙해져야 한다.
문제 해석
#1. N개의 회의에 대해 회의실 사용표를 만들려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고 각회의가 겹치지 않게 회의실 사용 표를 만들어라
#2. 단 회의 시작시간과 끝나는시간이 같을수는 있다.
#생각
#1. 이 문제에 가장 큰 힌트는 끝나는 시간에 있다. 끝나는 시간이 빠른 순으로 정렬을 한다.
#2. 이후에 다음 회의의 시작시간과 전 회의의 끝나는 시간이 겹치지 않으면 카운트를 해 준다.
문제 자체는 간단한 문제이다.
생각에 대한 내 코드이다.
import sys
N = int(sys.stdin.readline())
lst = list()
for i in range(N):
lst.append(list(map(int,sys.stdin.readline().split())))
lst.sort(key=lambda x:(x[1],x[0]))
cnt = 1
last_end_time = lst[0][1]
for i in range(0,N-1):# 시작시간이 처음의 끝시간보다 작으면 안됨
if last_end_time <= lst[i+1][0]:
cnt = cnt + 1
last_end_time = lst[i+1][1]
print(cnt)
중간에 있는 sort 부분은 이차원 리스트 형태로 받아온 자료에 대해서, 1번 인덱스 먼저 정렬 후 , 0번 인덱스로 정렬한다는 의미이다.
'코딩테스트 > 백준 알고리즘 풀이' 카테고리의 다른 글
[백준 알고리즘/Python] 백준 15686번 치킨 배달, 파이썬 설명 (0) | 2022.03.27 |
---|---|
[백준 알고리즘/Python] 백준 112100번 2048 (Easy), 파이썬 설명 (0) | 2022.03.23 |
[백준 알고리즘/python] 백준 11047번 동전 0, 파이썬 설명 (1) | 2020.09.27 |
[백준 알고리즘/python] 백준 1436번 영화감독 숌, 파이썬 설명 (0) | 2020.09.27 |
[백준 알고리즘/python] 백준 1018번 체스판 다시 칠하기, 파이썬 설명 (2) | 2020.09.13 |
댓글