다이나믹 프로그래밍 연습하기 -수영장-

1. 문제

 

1952. [모의 SW 역량테스트] 수영장

 

SW Expert Academy

SW Expert Academy

 

 

1일 이용권, 1달 이용권, 3달 이용권, 1년 이용권을 사용하여  주어진 1월~12월까지 수영장 이용 계획을 최소 비용으로 이용하고 싶을때, 그러한 최소 비용을 찾는 문제

 

 

2. 풀이

 

다이나믹 프로그래밍을 연습할 수 있는 아주 좋은 문제다

 

dp[i]를 1~i번째 달까지 사용한 최소 요금으로 정의하자

 

각각의 i번째 달에 사용할 수 있는 경우의 수는 무엇일까?

 

 

1) 1일 이용권을 모두 사용하는 경우

 

예를 들어 3월에 2일 사용했는데, 2일을 1일 이용권 2번으로 사용할 수 있다

 

2) 1달 이용권을 사용하는 경우

 

1달 이용권 1개로, 각 달의 사용 일수에 상관 없이 모두 사용가능하다

 

3) 3달 이용권을 사용하는 경우

 

4) 1년 이용권을 사용하는 경우

 

이 4가지가 모두 i번째 달에 최소로 요금을 사용할 수 있는 배타적인 관계이다.

 

예를 들어 3월에 2일을 사용할려고 하는데, 1일 이용권 1개 사고, 1달 이용권 1개 사면.. 당연히 돈낭비이다.

 

그래서 기본적으로 i번째 달까지 사용한 최소 요금 비용은...

 

이전 달인 i-1번째 달까지 사용한 최소 요금 비용 + i번째 달에 최소로 사용한 최소 요금 비용

 

#################################################################################

 

그런데, "i번째 달에 최소로 사용한 최소 요금 비용"은?

 

(1일 이용권 가격* 사용일수)과 (1달 이용권 가격)과 (3달 이용권 가격)과 (1년 이용권 가격).. 중 최솟값일 것이다.

 

그러므로..

 

$dp[i] = min( dp[i-1] + (1일 이용권 가격* 사용일수) , dp[i-1] + (1달 이용권 가격), dp[i-1] + (3달 이용권 가격), dp[i-1] + (1년 이용권 가격) )$

 

그런데.. 당연히 이상한 점이 있다

 

최솟값으로 비용을 지불하고 싶다면.. 당연히 1달마다 3달 이용권을 사고, 1달마다 1년 이용권을 사는것은 돈낭비이다

 

3달 이용권은 1번 사면 3달간 사용할 수 있고 1년 이용권은 1번 사면 1년간 사용할 수 있다

 

이걸 어떻게 처리할 수 있을까? 생각보다 간단하다

 

3달 이용권을 사고 싶다면.. 3달에 1번씩 사면 된다

 

(3달 전의 최소 요금 비용) + (3달 이용권 가격)  = dp[i-3] + (3달 이용권 가격)

 

1년 이용권을 사고 싶다면? 1년에 1번만 사면 된다

 

(1년 전의 최소 요금 비용) + (1년 이용권 가격) = dp[i-12] + (1년 이용권 가격)

 

그러므로 최종적으로 경우의 수를 생각해보면..

 

최초 1월과 2월에는 3달 이용권을 구매할 수 없다

 

문제 조건에도 명시되어 있음

 

" 다음 해의 이용권만을 구매할 수 있기 때문에 3달 이용권은 11월, 12월, 1윌 이나 12월, 1월, 2월 동안 사용하도록 구매할 수는 없다."

 

그러므로 1월과 2월까지 사용한 최소 요금 비용은.. 1일 이용권, 1달 이용권만을 구매하였을때 최소 비용이다.

 

i <= 2에서, dp[i] = min(dp[i-1] + (1일 이용권)*(사용일수), dp[i-1] + (1달 이용권))

 

3월부터 11월까지 사용한 최소 요금 비용은... 

 

3월부터는 3달 이용권을 구매한 경우가 포함된다.. 1월부터 3달 이용권을 구매해놓으면 3월에 정산이 되는거야

 

그래서 1일,1달,3달 이용권만을 구매하였을때 최소 비용이다.

 

i <=11에서, dp[i] = min(dp[i-1] + (1일 이용권)*(사용일수), dp[i-1]+(1달이용권), dp[i-3]+(3달 이용권))

 

12월에 사용한 최소 요금 비용은...?

 

이제는 1년 이용권을 구매한 경우도 포함된다. 1월에 1년 이용권을 구매했으면.. 12월에 정산이 되는거야

 

그래서 1일,1달,3달,1년 이용권을 구매한 것중에 최소 비용이다.

 

i == 12에서.. dp[i] = min(dp[i-1] + (1일 이용권)*(사용일수), dp[i-1]+(1달 이용권), dp[i-3]+(3달 이용권), dp[i-12]+(1년 이용권))

 

이러면 최소 비용이 월마다 누적되면서, 최종 12월에, 12월까지 사용한 최소 요금 비용이 저장된다

 

#다이나믹 프로그래밍
T = int(input())

for tc in range(1,T+1):
    
    d,m,q,y = map(int,input().split())  #1일,1달,3달,1년

    year_list = [0] + list(map(int,input().split())) ##1년 이용계획 0~11에 인덱스를 위해 [0]을 추가

    dp = [0]*13 ##dp[i]: i달까지 사용된 최소 요금 비용

    for i in range(1,13):
        
        ##2월까지 최소비용
        ##이전 월의 최소비용+1일요금*이용일과 이전 월의 최소비용+1달비용중 최솟값
        if i <= 2:
            
            dp[i] = min(dp[i-1]+d*year_list[i],dp[i-1]+m)
        
        ##3월부터는 3개월 이용권을 구입 가능
        ##이전 월까지의 최소 비용+1일요금*이용일과 이전 월의 최소비용+1달비용과 3개월전의 최소비용+3달비용중 최솟값
        elif i <= 11:
            
            dp[i] = min(dp[i-1]+d*year_list[i],dp[i-1]+m,dp[i-3]+q)
        
        
        ##마지막해에는 1년 이용권을 구입 가능
        
        ##이전 월까지의 최소 비용+1일요금*이용일과 이전 월의 최소비용+1달비용과 3개월전의 최소비용+3달비용과 1년전 최소비용+1년비용중 최솟값
        else:
            
            dp[i] = min(dp[i-1]+d*year_list[i], dp[i-1]+m, dp[i-3]+q, dp[i-12]+y)

    
    print('#'+str(tc),dp[12])