[백준] 2457 공주님의 정원 greedy python 골3

처음에는 아래와 같이 풀려고 했다

 

3월 1일보다 시작일이 같거나 작은 첫번째 꽃을 고르고

(만약 종료일이 이전 꽃보다 길다면 그 꽃을 시작 꽃으로 지정)

 

그리고 그 외에 시작일이 3월 1일이 아닌 꽃들은 

이전꽃의 종료일보다 현재 꽃의 시작일이 작거나 같으면 그 꽃으로 갱신

만약 이전 꽃의 종료일보다 현재 꽃의 종료일이 늦으면 현재 꽃으로 갱신

 

이런식으로 풀어가려고 했다

 

그 이유는 예제로 시뮬레이션을 돌린 후 그 과정을 그대로 코드로 구현하고자 했기 때문..

 

하지만 잘 작동하지 않앗다

 

<틀린 풀이>

n = int(input())
flower=[]
for i in range(n):
    a,b,c,d = map(int,input().split())
    start = int(str(a)+str(format(b,'02')))
    end = int(str(c)+str(format(d,'02')))

    flower.append([start,end])

flower.sort()
print(flower)

count=1
current=flower[0]
for i in flower:
    if i[0]<=301:
        if current[1]<i[1]:
            current=i
            print("<301", current)
    else:
        if current[1]>i[0]:
            count+=1
            current=i
            print("update", current)
        if current[1]<i[1]:
            current=i
            print("update by end", current)
            if current[1]>=1130:
                break

print(count)

 

 

결국 다른 풀이를 참고했는데

접근법은 비슷할지 몰라도 과정은 좀 많이 달랐다

 

while문을 써서 i를 직접 경우에 따라 증가시키는 방식으로 사용

 

현재 꽃의 개화 시기 사이에 마지막 꽃의 종료일이 존재한다면

다음 꽃을 탐색하면서 가장 늦게 지는 꽃을 고르고

꽃의 개수가 마지막 꽃의 종료일을 업데이트

 

만약 종료일이 1130을 초과하면 프로그램 종료

 

n = int(input())
flower=[list(map(int,input().split())) for _ in range(n)]

flower.sort()

i=0
result=0
last_end = (3,1)

while i<n:
    sm,sd,em,ed = flower[i]
    if (sm,sd) <= last_end < (em,ed):
        max_end = (em,ed)
        while i<n-1:
            nsm,nsd,nem,ned = flower[i+1]
            if last_end<(nsm,nsd):
                break
            if max_end<(nem,ned):
                max_end=(nem,ned)
            i+=1
        result+=1
        last_end=max_end
        if(11,30)<last_end:
            print(result)
            exit(0)
    i+=1
print(0)



# 0301 부터 1130까지