[BOJ] 백준 2457 공주님의 정원 (Python)

문제

2457번: 공주님의 정원

 

문제 해석

접근 방법

그리디 알고리즘과 정렬을 사용해 풀이할 수 있는 문제입니다. 현재 선택할 수 있는 꽃 중에서 가장 늦게 지는 꽃을 선택해나가면 최소한의 개수로 조건을 만족할 수 있습니다.

 

(매일 꽃이 한 가지 이상만 피어 있으면 된다는 조건 때문에 그리디 알고리즘을 사용했습니다. 구간의 중복을 고려하지 않고 가장 늦게 지는 꽃을 선택할 수 있기 때문입니다. 만약 조건이 바뀌어 하루에 꽃이 단 한 송이만 피어 있어야 한다면 다른 풀이법(dp 등)을 사용해야 할 것입니다)

 

풀이 과정

풀이 과정을 요약하면 다음과 같습니다.

1. 제시된 꽃들을 피는 날짜 기준 오름차순으로 정렬합니다.
2. 꽃이 피는 날짜의 범위 설정 후 조건에 맞는 꽃(현재 선택할 수 있는 꽃)을 탐색합니다.
3. 그 중 가장 늦게 지는 꽃을 선택합니다.
4. 선택한 꽃의 지는 날짜가 특정 조건에 걸린다면 탐색을 종료합니다.
    4-1. 만약 선택한 꽃이 11월 30일 이후에 지는 경우, 탐색 종료 후 사용된 꽃 개수를 반환합니다.
    4-2. 만약 선택한 꽃이 지는 날짜가 2.의 피는 날짜 범위를 벗어나지 못하는 경우 탐색 종료 후 0을 반환합니다.
5. 4의 조건에 걸리지 않는다면 사용한 꽃 개수에 +1을 한 후에 2~4 과정을 반복합니다.

 

먼저 현재 선택할 수 있는 꽃이란 직전에 선택한 꽃이 지기 전에 피는 꽃입니다.

ex) 만약 직전에 선택한 꽃이 5월 20일에 진다면, 현재 선택할 수 있는 꽃은 5월 20일 이전에 피는 꽃

 

따라서, 현재 선택할 수 있는 꽃은 피는 날짜에 의해 결정되므로 피는 날짜를 기준으로 오름차순으로 정렬합니다. 이때 기준 (sort의 key)을 설정하기 위해서 lambda를 사용합니다.

 

• lambda : 일회성 함수를 익명 함수로 간단하게 작성하는 키워드로 map, sort, sorted 등의 키워드와 함께 자주 사용함

lambda x : f(x) # x를 f(x)로 return

# map과 함께 사용하기

numbers = [1, 2, 3, 4]
mapped_numbers = list(map(lambda x: x*2, numbers))

print(mapped_numbers) # [2, 4, 6, 8]


# sorted와 함께 사용하기

students = [{"name": "chop", "grade": 10}, {
    "name": "pop", "grade": 12}, {"name": "hop", "grade": 8}]
sorted_arr = sorted(students, key=lambda x: x["grade"]) # 각 원소의 "grade" 기준으로 오름차순 정렬

print(sorted_arr) # [{"name": "hop", "grade": 8}, {"name": "chop", "grade": 10}, {"name": "pop", "grade": 12}]

 

 

정렬이 끝났다면 이제 피어있는 날짜가 서로 연속되도록 꽃을 선택합니다.

첫 번째 탐색에서는 문제 조건에 따라 피는 날짜가 1월 1일과 3월 1일 사이에 존재하는 모든 꽃을 탐색한 후, 이 중에서 가장 늦게 지는 꽃을 선택합니다. 예제 1번에서는  1 1 5 31과  1 1 6 30 중에서 1 1 6 30을 선택하게 됩니다.

 

 

그리고 선택한 꽃이 지는 날짜에 따라서 탐색을 계속할지 결정합니다.

• 만약 선택한 꽃의 지는 날짜가 3월 1일 이전이라면 다음 날짜를 확보할 수 없으므로 탐색을 종료합니다.
• 만약 선택한 꽃의 지는 날짜가 11월 30일 이후라면 문제의 조건을 이미 만족했으므로 탐색을 종료합니다. 이때 사용한 꽃 개수에 현재 선택한 꽃을 포함해야 하므로 1을 더해줍니다.

 

위 조건에 따라 탐색이 종료되지 않았다면 사용한 꽃 개수에 1을 더해준 후 두 번째 탐색을 시작합니다.

두 번째 탐색에서 꽃이 피는 날짜의 범위는 3월 1일과 6월 30일 사이가 됩니다. 종료 조건을 만날 때까지 해당 과정을 반복하면 사용한 꽃 개수를 도출할 수 있습니다.

 

예제 1번에서는 5 15 8 31과 6 10 12 10 중에서 6 10 12 10을 선택하게 되는데, 꽃이 지는 날짜 12월 10일은 11월 30일 이후이므로 탐색을 종료합니다. 두 번째 탐색을 마쳤으므로 사용한 꽃의 개수는 2가 됩니다.

 

전체 코드

from sys import stdin

N = int(stdin.readline().rstrip())
arr = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]

# 날짜 대소 비교를 위해 월,일을 숫자로 변환 ex) 1월 1일 > 101
flowers = [[x[0]*100+x[1], x[2]*100+x[3]] for x in arr]
flowers.sort(key=lambda x: x[0])

def count_flowers():
    period = [101, 301]
    idx, cnt = 0, 0

    while period[1] <= 1130:
        temp_end = period[0]
        for i in range(idx, N):
        
            if period[0] <= flowers[i][0] <= period[1]:
                if flowers[i][1] > 1130:
                    cnt += 1
                    return cnt
                if flowers[i][1] >= temp_end:
                    temp_end = flowers[i][1]
                idx = i+1
            else:
                break
                
        if temp_end <= period[1]:
            return 0
        else:
            cnt += 1
            period = [period[1], temp_end]

    return cnt

print(count_flowers())