[모의 SW 역량 테스트] 1952 수영장 (Python)

출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq

 

문제

김 프로는 수영장을 이용한다.

김 프로는 지출이 너무 많아 1년 동안 각 달의 이용 계획을 수립하고 가장 적은 비용으로 수영장을 이용할 수 있는 방법을 찾고 있다.

수영장에서 판매하고 있는 이용권은 아래와 같이 4 종류이다.

   ① 1일 이용권 : 1일 이용이 가능하다.

   ② 1달 이용권 : 1달 동안 이용이 가능하다. 1달 이용권은 매달 1일부터 시작한다.

   ③ 3달 이용권 : 3달 동안 이용이 가능하다. 3달 이용권은 매달 1일부터 시작한다.
       (11월, 12월에도 3달 이용권을 사용할 수 있다)

   ④ 1년 이용권 : 1년 동안 이용이 가능하다. 1년 이용권은 매년 1월 1일부터 시작한다.

각 달의 이용 계획은 [Table 1]의 형태로 수립된다.

이용 계획에 나타나는 숫자는 해당 달에 수영장을 이용할 날의 수를 의미한다.

각 이용권의 요금과 각 달의 이용 계획이 입력으로 주어질 때,

가장 적은 비용으로 수영장을 이용할 수 있는 방법을 찾고 그 비용을 정답으로 출력하는 프로그램을 작성하라.


[예시]

수영장에서 판매하는 1일 이용권, 1달 이용권, 3달 이용권, 1년 이용권의 요금은 각각 10원, 40원, 100원, 300원이다.

이 때 수영장을 이용할 수 있는 방법은 [Table 2]와 같이 다양한 경우를 생각할 수 있다.

 

다른 경우도 가능하지만, 가장 적은 비용으로 수영장을 이용한 경우는 4번 경우이다.

따라서, 정답은 110이 된다.


[제약 사항]

1. 시간 제한 : 최대 50개 테스트 케이스를 모두 통과하는 데 C/C++/Java 모두 3초

2. 모든 종류의 이용권 요금은 10 이상 3,000 이하의 정수이다.

3. 각 달의 이용 계획은 각 달의 마지막 일자보다 크지 않다.

[입력]

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 1일 이용권의 요금, 1달 이용권의 요금, 3달 이용권의 요금, 1년 이용권의 요금이 순서대로 한 칸씩 띄고 주어진다.

그 다음 줄에는 1월부터 12월까지의 이용 계획이 주어진다.

[출력]

테스트 케이스 개수만큼 T개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.

각 줄은 "#t"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (t는 1부터 시작하는 테스트 케이스의 번호이다)

출력해야 할 정답은 이용 계획대로 수영장을 이용하는 경우 중 가장 적게 지출하는 비용이다.

 

10      // 총 테스트 케이스 개수 T = 10 10 40 100 300   // 첫 번째 테스트 케이스, 이용권 가격들 0 0 2 9 1 5 0 0 0 0 0 0 // 12개월 이용 계획 10 100 50 300    // 두 번째 테스트 케이스, 이용권 가격들 0 0 0 0 0 0 0 0 6 2 7 8 // 12개월 이용 계획 …

#1 110 #2 100 #3 400 #4 530 #5 430 #6 1080 #7 1840 #8 800 #9 1980 #10 2260

 

풀이

각 월을 깊이로서 DFS 탐색을 하여 문제를 해결함. 운영계획이 존재하는 월이라면 이용권(1일,1달,3달,1년)에 대한 비용을 적용시키고, 이용일수에 맞춰 깊이를 추가하여 다시 재귀를 타고 하나의 조합이 완료되면 최소비용인지 비교를 함으로써 문제를 해결하였다.

 

코드

def swim(idx,money):
    global min_price
    if idx >= 12: 
        if money < min_price: # 최소 비용 비교 
            min_price = money
        return
    if plan[idx]: # 운영 계획이 존재 할 때
        for i in range(4): # 비용을 기준으로 탐색하므로 비용의 개수인 4번만큼 반복
            if i == 0: # 1일권 
                swim(idx+1,money+price[i]*plan[idx])
            elif i == 1: # 1달권
                swim(idx+1,money+price[i])
            elif i == 2: # 3개월권
                swim(idx+3,money+price[i])
            else: # 1년권
                swim(idx+12,money + price[i])
    else: # 운영계획이 존재 안한다면 idx를 1만큼 늘려서 다시 탐색
        swim(idx+1,money)
 
T = int(input())
for t in range(T):
    price = list(map(int,input().split()))
    plan = list(map(int,input().split()))
    min_price = 99999999
 
    swim(0,0)
    print('#{} {}'.format(t+1,min_price))