BOJ 2457번: 공주님의 정원

https://www.acmicpc.net/problem/2457

2457번: 공주님의 정원

3월 1일을 포함하는 날짜를 가진 꽃 중에 지는 날이 제일 먼 꽃을 선택하여 그 꽃이 지는 날을 다시 시작날짜로 놓고, 이 과정을 반복해서 시작 날짜가 11월 30일보다 커지면 ans를 출력한다.

비교를 쉽게 하기 위해 날짜를 숫자로 변환한다 ex) 3월 1일 = 301, 11월 30일 = 1130

또한 정렬을 통해 O(N)시간 안에 탐색이 가능하도록 한다.

 

꽃 배열을 돌다가 꽃의 피는 날짜가 현재의 피는날짜보다 커지는 경우 즉, 절대로 현재의 피는 날짜를 포함할 수 없는 경우에 ans를 하나 증가시키고 현재의 피는 날짜를 갱신한다. 중간에 피는날짜가 1130보다 커지면 바로 종료한다.

for 문을 모두 돈 후에 업데이트가 안될 수 있으므로 마지막으로 한 번 더 점검한다.

 

4%에서 계속 틀려서 멘붕오던 와중 질문에 데이터 추가 부분에 있는 반례를 보고 문제점을 깨닳았다. 처음에는 현재의 피는날짜를 포함하지 않는 꽃이 나오면 바로 갱신했는데, 꽃의 피는 날짜가 현재의 피는날짜보다 작다면 그 이후에 나오는 꽃이 현재의 피는 날짜를 포함할 가능성이 있기 때문에 그것까지 탐색해보아야  했다.

 

오래 걸렸지만 그래도 내 힘으로 풀어서 뿌듯하다,, 하하,,

import sys
input = sys.stdin.readline

N = int(input())
flower = []
for _ in range(N):
    a, b, c, d = map(int, input().split())
    flower.append([a*100+b, c*100+d])

flower.sort()

ans = 0
days = [301, 1130]
month, day = 0, 0
#print(flower)

for i in range(N):
    if (flower[i][0] <= days[0] < flower[i][1]):
        day = max(day,flower[i][1]) #지는날
    
    elif (flower[i][0] > days[0]):
        ans += 1
        days[0] = day
        day = 0
        if (flower[i][0] <= days[0] < flower[i][1]):
            day = flower[i][1]
    #print(days, i)
    if (days[0]>days[1]):
        print(ans)
        sys.exit(0)
        
if (day>days[1]):
    ans+=1
    print(ans)
else:
    print(0)