문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog
2457번: 공주님의 정원 문제보기
시간 제한: 1 초
메모리 제한: 192 MB
문제
오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다.
총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. (올해는 4, 6, 9, 11월은 30일까지 있고, 1, 3, 5, 7, 8, 10, 12월은 31일까지 있으며, 2월은 28일까지만 있다.)
이러한 N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다.
- 공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.
- 정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다.
N개의 꽃들 중에서 위의 두 조건을 만족하는, 즉 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, 3 8 7 31은 꽃이 3월 8일에 피어서 7월 31일에 진다는 것을 나타낸다.
출력
첫째 줄에 선택한 꽃들의 최소 개수를 출력한다. 만약 두 조건을 만족하는 꽃들을 선택할 수 없다면 0을 출력한다.
예제 입력 1
4
1 1 5 31
1 1 6 30
5 15 8 31
6 10 12 10
예제 출력 1
2
예제 입력 2
10
2 15 3 23
4 12 6 5
5 2 5 31
9 14 12 24
6 15 9 3
6 3 6 15
2 28 4 25
6 15 9 27
10 5 12 31
7 14 9 1
예제 출력 2
5
문제를 다시 요약하자면 3월 1일부터 11월 30일까지 꽃이 항상 보이게 심을 꽃의 개수를 구하는 문제이다.
예제 1을 보자.
target은 최소 이날 전에는 피는 꽃의 피는 날 한계 날짜이다
end는 모든 꽃을 확인해서 1201 이상 동안 꽃이 피어 있어야 하는 기록지이다.
1. [101,531]인 꽃은 target=301이전에 피고 end=0보다 오래 간다. target,end=[301,531] 그리고 꽃을 리스트에서 제거
2. [101,631]인 꽃은 target=301이전에 피고 end=531보다 오래 간다. target,end=[301,630] 그리고 꽃을 리스테에서 제거
3. [515,831]인 꽃은 target=301이후에 피기 때문에 마지막 심은 꽃에 대해 마지막 심은 꽃의 end를 target=630로 업데이트 해주고 마지막 꽃(2번꽃)을 심어준다 cnt+=1
또한 831일까지 가기 때문에 end=831로 업데이트 해준다. target,end=[630,831] 그리고 꽃을 리스테에서 제거
4. [610,1210]인 꽃은 target=630이전에 피고 end=831보다 오래 간다. 따라서 4번 꽃을 심어준다. cnt+=1
target,end=[630,1210]
정답 코드
import sys
# sys.stdin=open('input.txt', 'r')
input=sys.stdin.readline
if __name__=="__main__":
N=int(input()) # 꽃들의 총 개수
date=[]
for _ in range(N):
ms,ds,me,de=map(int,input().split())
date.append([ms*100+ds,me*100+de])
# 꽃이 피는 날짜 기준으로 오름차순으로 정렬, 가장 빨리 피는 꽃이 먼저
date.sort(key=lambda x: (x[0],x[1]))
cnt=0 # 선택한 꽃의 개수
end=0 # 제일 늦게 지는 꽃을 비교
target=301 # 마지막 꽃이 지는 날 업데이트, 가장 작은 값인 3월1일로 초기화
# 모든 꽃이 없어질 때까지 반복하여 꽃을 비교한다.
while date:
# 마지막 꽃의 지는 날이 12월1일보다 크거나 같을때 또는
# 마지막 꽃의 지는 날이 제일 빨리 피는 꽃보다 작으면 그만
if target>=1201 or target<date[0][0]:
break
# 주어진 꽃의 개수만큼 반복하여 구간별로 꽃을 비교하고
for _ in range(len(date)):
if target>=date[0][0]: # 마지막 꽃의 지는 날(target)이 제일 빨리 피는 꽃의 피는 날보다 크거나 같으면
if end<date[0][1]: # 현재 꽃이 지는 날이 더 크면 더 오래 꽃을 볼 수 있으므로
end=date[0][1] # 현재 꽃이 지는 날을 마지막 꽃의 지는 날로 업데이트
date.remove(date[0]) # 현재 꽃 심고 리스트에서 제거
else: # 마지막 꽃의 지는 날(target)보다 제일 빨리 피는 꽃의 피는 날이 더 크면
break
# 현재 꽃 date[0]에 대해 꽃을 심었으면
target=end # 마지막 꽃의 지는 날(target)은 심은 꽃의 지는날(end)로 바꿔준다
cnt+=1 # 꽃을 심었으므로 카운트
if target<1201:
print(0)
else:
print(cnt)
