[BOJ/백준] 13302 리조트 - 파이썬

문제

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

13302번: 리조트

 

 

문제풀이

1일권, 3일권, 5일권과 그에 따른 쿠폰을 사용해서 리조트 이용을 위한 최소 비용을 구하는 dp 문제이다.

bottom-up 방식으로 각각 날에 대해 dp 값을 갱신해주었다.

dp[day][coupon]으로 2차원 dp 배열을 선언해서 이용권에 따라 쿠폰 값도 갱신해주었다.

1일권 구매	dp[i+1][j]=min(result+10000 , dp[i+1][j])
3일권 구매	dp[i+k][j+1]=min(result+25000 , dp[i+k][j+1]) ##k=1,2,3
5일권 구매	dp[i+k][j+2]=min(result + 37000 , dp[i+k][j+2])  ##k=1,2,3,4,5
쿠폰 3장 이상	dp[i+1][j-3]=min(result,dp[i+1][j-3])
리조트 방문 X	dp[i+1][j]=min(result,dp[i+1][j])

 

 

 

코드

import sys
input=sys.stdin.readline

n,m=map(int,input().split()) #n<=100
no=list(map(int,input().split()))
inf=sys.maxsize

dp=[[inf]*106 for _ in range(106)]
dp[0][0]=0

for i in range(n+1):
    for j in range(40): ##최대 쿠폰 발행 갯수 ==40개
        if dp[i][j]==inf:
            continue
        result=dp[i][j]
        if i+1 in no:
            dp[i+1][j]=min(result,dp[i+1][j])
        if j>=3:
            dp[i+1][j-3]=min(result,dp[i+1][j-3])
            
        #1일권
        dp[i+1][j]=min(dp[i+1][j],result+10000)
        #3일권
        for k in range(1,4):
            dp[i+k][j+1]=min(dp[i+k][j+1],result+25000)
        #5일권
        k=0
        for k in range(1,6):
            dp[i+k][j+2]=min(dp[i+k][j+2],result+37000)
print(min(dp[n]))

 

 

어려웠던 점

첫날에 3일권을 구입하면 둘째 날에도 25000원 지불과 쿠폰 1장 보유는 적용되어야 하기 때문에

매일매일 값을 갱신해 주어야 한다.

처음에 3일권, 5일권을 구매할 때 [i+3] 일과 [i+5] 일만 계산하면 된다고 생각해서 틀렸었다