[ Baekjoon - 10/17 ] - 2457번: 공주님의 정원

• 문제 링크 : https://www.acmicpc.net/problem/2457

2457번: 공주님의 정원

 

• 소요 시간 : 3시간

 

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초
     • 메모리 : 192MB
   • 문제
     
     • N개의 꽃(1≤N≤100,000)
     • 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어있어야 하고, 가능한 정원에 심는 꽃들의 수를 가능한 적게 해야한다.
   • 이해
     • 조건대로 수행하면 되는데, 이제 어떻게 접근하여 최적화 할지 생각해야하는 문제이다.
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 입출력 형태와 조건을 적어보았고, 기간으로 판단하는 문제이므로 어떤형태로 올수있는지 넘버링하며 적어보았다. 그리디 적으로 접근해야할것같긴한데 확실한 방법이 떠오르진 않아 해결방법을 고민했다.
3. 문제를 어떻게 해결할 것인가
   • 1st 접근 - 거의 세그먼트 트리? )

     • 

     • 12개의 월에 각각 있는 날짜를 자식으로 넣어두고 해당날짜가 포함될때마다 +1을 해준다.
     • 해당 배열 중 3월 1일~11월 30일에 속하는 부분중에서 최솟값이 가능한 경우의 수라 생각해서 그려본 접근이었다.
     • 지금은 문제를 완전히 풀고 이해한 상태라 잘못된 접근이라는것을 알고있지만, 풀때는 저 방법이 정확하다고 생각해서 시간을 많이 쏟았다.. 문제에서 주어진 두번째 입출력 케이스만 넣어봐도 맞지 않다는걸 알수있지만 하나만 해보고 맞다 생각한 착오였다..
   • 2nd 접근 -  그리디 )
     • 빨리 개화하는 순서대로 정렬한 후, 이를 순회하며
       현재 피어 있는 꽃이 지기 전에 피고, 그 중 가장 늦게 지는 꽃을 선택하면 꽃을 최소의 개수로 선택한다.
4. 위 계획을 검증
   • 그리디의 흔한 유형중 하나라 생략
5. 계획 수행 (실제코드 작성)
   1. Python 3

      • import sys
        input = sys.stdin.readline
        
        N = int(input())
        flowers = []
        
        # 이전 월의 누적 일수
        month = {'1': 0, '2':31, '3':59, '4':90, '5':120, '6':151, '7':181, '8':212, '9':243, '10':273, '11':304, '12':334}
        for i in range(N):
            flower = list(input().split())
            start = month[flower[0]] + int(flower[1])
            end = month[flower[2]] + int(flower[3])
            flowers.append([start, end])
        flowers.sort()
        
        fadeDates = 60
        cnt = 0
        tmp = 0
        
        for flower in flowers:
            if flower[0] > fadeDates:
                if tmp and flower[0] - tmp <= 0:
                    cnt += 1
                    fadeDates = tmp
                    tmp = 0
                    if fadeDates > 334:
                        break
                else:
                    cnt = 0
                    break
            tmp = max(tmp, flower[1])
        else:
            if tmp:
                cnt += 1
                if tmp <= 334:
                    cnt = 0
        print(cnt)

 

• 결과