알고리즘/BOJ
[BOJ 2457, Python 3] 공주님의 정원
70825
2021. 8. 14. 00:21
반응형
https://www.acmicpc.net/problem/2457
2457번: 공주님의 정원
첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서,
www.acmicpc.net
풀이
회의실 배정 문제랑 비슷한데, 날짜 처리도 그렇고 꽃이 지기 전에 꽃을 미리 구해놔야해서 생각하기가 좀 까다로웠던 문제였습니다.
일단 값을 받을 때 날짜를 1월 1일이면 101, 12월 31일이면 1231처럼 월에 100을 곱해줘서 일이랑 더해줍니다. 다 했으면 이제 날짜순으로 오름차순 정렬을 해주면 됩니다.
그리고 먼저 3월 1일 이전에 꽃이 피면서 제일 늦게 지는 꽃을 구합니다.(꽃이 지는 날을 e라고 합시다.)
그 후부터는 for문을 이용해 꽃이 피는 날이 e 이전이면서 꽃이 가장 늦게 지는 꽃을 찾아서 업데이트 해줍니다.
배열을 오름차순으로 정렬했으므로 e를 업데이트 했으면 이전에 봤던 꽃은 볼 필요가 없으니 한 번도 확인하지 않은 제일 작은 인덱스부터 꽃이 피는 날이 e 이전이면서 꽃이 가장 늦게 지는 꽃을 찾아서 e의 값이 1130이상이 될 때까지 업데이트를 반복하면 됩니다.
0을 출력하는 것은 꽃이 지는 날이 e보다 클 경우입니다. 날짜순으로 오름차순 정렬했으니 꽃이 피는 날이 e보다 크면 나머지 꽃들도 전부 e보다 크다는 것이 보장되어 있습니다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
input = __import__('sys').stdin.readline
n = int(input())
arr = []
for i in range(n):
a, b, c, d = map(int, input().split())
if 100*c+d < 301 or 100*a+b > 1130: continue
arr.append([100*a+b, 100*c+d])
arr.sort()
flower = [-1, -1]
idx = -1
for i in range(n):
if arr[i][0] > 301: break
if arr[i][1] > flower[1]:
flower = arr[i]
idx = i
ans = 1
day = flower[1]
while day <= 1130:
next_flower = [-1, -1]
for i in range(idx, n):
if arr[i][0] > day: break
if flower[0] < arr[i][0] <= flower[1] < arr[i][1]:
if arr[i][1] > next_flower[1]:
next_flower = arr[i]
idx = i
if next_flower[0] == -1:
print(0)
exit()
flower = next_flower
day = flower[1]
ans += 1
print(ans)
|
cs |
반응형