포도가게의 개발일지
python 백준 1931 회의실 배정 본문
반응형
https://www.acmicpc.net/problem/1931
문제 : 가장 많이 회의실을 쓸 수 있도록 배치
접근법
- 그리디 알고리즘 문제였다
- 그리디 알고리즘은 subprob에서 최적의 해가 전체 prob에서 최적의 해가 되는 것을 증명하는 문제이다
- 그래서 저는 시작 시간, 끝나느 시간, 시간의 차이로 매트릭스에 저장 후
- 우선 정렬을 끝나는 시간으로 순서대로 정렬 하였다. 힌트가 큰 도움이 됬다. -> 다음 정렬은 스타트 시간을 순서대로 정렬한다.
- 그리디 알고리즘은 subprob에서 최적의 해가 전체 prob에 최적의 해가 부정되는 순간 문제자체가 성립 될 수 없다.
- 그리디 알고리즘으로 문제를 냈다는 것은 위에 과정이 성립될 수 밖에 없단거였고 나는 subprob에서 최적의 해만 찾으면 된다.
import sys
sys.stdin = open('inputs.text')
matrix = []
n = int(sys.stdin.readline())
for _ in range(n):
a,b = map(int,sys.stdin.readline().split())
dif = b - a
matrix.append([a,b,dif])
matrix.sort(key=lambda x: (x[1],x[0]))
start,end,diff = matrix.pop(0)
result = []
result.append([start,end,diff])
while matrix:
start2,end2,diff2 = matrix.pop(0)
if start2>=end:
result.append([start2,end2,diff2])
start=start2
end=end2
diff=diff2
print(len(result))
'백준' 카테고리의 다른 글
python 백준 5557 1학년(dp) (0) | 2021.09.01 |
---|---|
python 백준 1946 신입사원 (0) | 2021.08.30 |
python 백준 1904 01타일 (0) | 2021.08.26 |
python 백준 2638 치즈 (0) | 2021.08.25 |
python 백준 16236 아기상어 (0) | 2021.08.24 |
Comments