[Python/백준] 2457 공주님의 정원

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

2457번: 공주님의 정원

 

<문제 해설>

그리디 문제이다. 문제자체는 간단하다 

1. 꽃이 피는 날자를 인덱스로 지는 날자를 저장할 배열을 만든다.
2. 처음 1월 1일부터 3월 1일안에 꽃이 피는 날자가 있는 꽃중 지는 날자가 가장 먼 꽃을 선택한다. 이유는 가장 먼 시간까지 살아있는 꽃이 더 많은 선택지를 줘서 원하는 값(목표)에 더 빠르게 접근할 수 있을테니 최소 개수를 출력하기 좋은 조건이 된다.
3. 이제 2에서 선택한 꽃이 피는 날자부터 지는 날자안에 피는 꽃중 지는 날자가 가장 먼 꽃을 선택한다. 
4. 2,3을 반복하다가 11월 30일보다 더 늦게 지면 몇개의 꽃을 선택했는지 숫자를 출력해주면 된다.
5. 만약 2에서 선택한 꽃이 지는 날자가 그전에 선택한 꽃보다 일찍 지거나 같은날 지면 기간안에 다른 꽃을 피우지 않아 정원에 꽃이 없다는 뜻이니 0을 출력한다.

살아있는 기간이 긴 꽃을 고른다는 것이 아니다. 꽃이 지는 날이 가장 늦게 지는 꽃을 고른 것이 핵심이다.

<예시>

이 사진은 문제의 예제입력 1을 표로 그린 것이다.  위에 설명한 방식을 따라가 보겠다.

1. 1월, 3월 안에 피는 꽃은 1,2 꽃이 있다 이중 꽃 2가 더 늦게 지니 꽃 2를 선택한다.
2. 꽃 2가 피는 날은 1월 1일이고 지는 날은 6월 30일이다. 이 기간안에 피는 꽃은 꽃 3,4가 있다 이중 꽃 4가 더 늦게 지니 꽃 4를 선택한다.
3. 꽃 4가 지는 날이 11월 30일보다 늦게진다. 따라서 꽃을 2번선택했고 답으로 2를 출력한다.

<코드>

코드 설명전에 얌심적으로 말할 것이 있다. 내가 짠코드에서 받아온 날자의 단위를 변경하면서 생긴 매우긴 라인들은(17~67)은 날자를 365일 처럼 바꾸는 것보다 월에 100을 곱해서 (ex: 12월 5일 -> 1205)로 바꾸는 방식이 더 보기 간단하고 배열의 공간 절약과 나중에 늦게 피는 꽃을 찾을 때의 시간도 절약할 수 있다. 이는 문제를 풀다가 11월달 날자 더하기를 1잘못적어서 틀린 적이있었어서 문제를 다시 제출해 맞은 이후 다른 분들의 코드를 보고 알았다. 이런 사고를 하려고 하지 않고 매우 효율적이지 않은 코드를 사용한 나를 기억하고 반성하기 위해서 기록하겠다.

def search(start,end):
    global count
    Maxalivetime = max(days[start:end+1])
    count += 1
    if Maxalivetime >= 335:
        print(count)
        return
    elif Maxalivetime <= end:
        print(0)
        return
    else:
        search(end,Maxalivetime)

import sys
N = int(sys.stdin.readline())

start = 60
days = [0]*366
for i in range(N):
    line = list(map(int,sys.stdin.readline().split()))
    startday = line[1]
    endday = line[3]
    if line[0] == 2:
        startday += 31
    elif line[0] == 3:
        startday += 59
    elif line[0] == 4:
        startday += 90
    elif line[0] == 5:
        startday += 120
    elif line[0] == 6:
        startday += 151
    elif line[0] == 7:
        startday += 181
    elif line[0] == 8:
        startday += 212
    elif line[0] == 9:
        startday += 243
    elif line[0] == 10:
        startday += 273
    elif line[0] == 11:
        startday += 304
    elif line[0] == 12:
        startday += 334
    if line[2] == 2:
        endday += 31
    elif line[2] == 3:
        endday += 59
    elif line[2] == 4:
        endday += 90
    elif line[2] == 5:
        endday += 120
    elif line[2] == 6:
        endday += 151
    elif line[2] == 7:
        endday += 181
    elif line[2] == 8:
        endday += 212
    elif line[2] == 9:
        endday += 243
    elif line[2] == 10:
        endday += 273
    elif line[2] == 11:
        endday += 304
    elif line[2] == 12:
        endday += 334
    days[startday]=max(endday,days[startday])
    
count = 0
search(0,start)

 

<코드 설명>

def search(start,end): //꽃을 찾았을시 그 꽃안에서 다시 찾는 재귀함수
    global count //꽃을 몇개 선택했는지 저장할 변수
    Maxalivetime = max(days[start:end+1]) //선택한 꽃이 살아있는 기간중에 피는 꽃중 가장 살아있는 시간이 긴 꽃을 선택한다.
    count += 1 //꽃을 선택했으니 값을 증가시켜준다.
    if Maxalivetime >= 335: //11월 31일보다 크거나 같으면 기간동안 적어도 1개의 꽃은 피운것이니 count출력
        print(count)
        return //더이상 찾을 필요없으니 재귀함수 종료
    elif Maxalivetime <= end: //위에서 설명했 듯 더이상 찾을 꽃이 없음으로 꽃이 적어도 1개도 피지 못했다.
        print(0) //0출력
        return
    else:
        search(end,Maxalivetime) //선택한 꽃의 기간을 넘겨주기 이전꽃의 지는 시기인 end 이전의 피는 꽃은 굳이 볼 필요없으니(max값에 이미 탈락했으니) 시작점으로 잡아준다.

import sys //sys라이브러리 불러오기
N = int(sys.stdin.readline()) //N값 정수로 받아오기

start = 60 //3월 1일보다 이전에 펴야하니 60일지정
days = [0]*366 //피는 날자를 인덱스로 쓰며 지는 날자를 저장할 배열
for i in range(N): //N만큼 반복하면서
    line = list(map(int,sys.stdin.readline().split())) //line에 한라인씩 받아온다
    startday = line[1] //피는 날자를 저장할 배열에 일을 넣어준다
    endday = line[3] //지는 날자를 저장할 배열에 일을 넣어준다
    if line[0] == 2: //아래로는 월이 몇월인지에 다라서 피는 날자, 지는 날자에 넣는 날이 주어진다.
        startday += 31
    elif line[0] == 3:
        startday += 59
    elif line[0] == 4:
        startday += 90
    elif line[0] == 5:
        startday += 120
    elif line[0] == 6:
        startday += 151
    elif line[0] == 7:
        startday += 181
    elif line[0] == 8:
        startday += 212
    elif line[0] == 9:
        startday += 243
    elif line[0] == 10:
        startday += 273
    elif line[0] == 11:
        startday += 304 //304로 해야했지만 303으로 해서 틀렸었다.
    elif line[0] == 12:
        startday += 334
    if line[2] == 2:
        endday += 31
    elif line[2] == 3:
        endday += 59
    elif line[2] == 4:
        endday += 90
    elif line[2] == 5:
        endday += 120
    elif line[2] == 6:
        endday += 151
    elif line[2] == 7:
        endday += 181
    elif line[2] == 8:
        endday += 212
    elif line[2] == 9:
        endday += 243
    elif line[2] == 10:
        endday += 273
    elif line[2] == 11:
        endday += 304
    elif line[2] == 12:
        endday += 334
    days[startday]=max(endday,days[startday]) //피는 날자가 겹치는 꽃이 있을 수 있으니 지는 기간이 더 먼 꽃을 넣어주자
    
count = 0 //꽃 선택수 0으로 초기화
search(0,start) //함수 호출