수영장 Python(SW Expert Academy, SWEA)

난이도 : 모의 SW 역량테스트

문제번호 : 1952

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq&categoryId=AV5PpFQaAQMDFAUq&categoryType=CODE

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

김 프로는 수영장을 이용한다. 김 프로는 지출이 너무 많아 내년 1년 동안 각 달의 이용 계획을 수립하고 가장 적은 비용으로 수영장을 이용할 수 있는 방법을 찾고 있다. 수영장에서 판매하고 있는 이용권은 아래와 같이 4 종류이다.    ① 1일 이용권 : 1일 이용이 가능하다.    ② 1달 이용권 : 1달 동안 이용이 가능하다. 1달 이용권은 매달 1일부터 시작한다.    ③ 3달 이용권 : 연속된 3달 동안 이용이 가능하다. 3달 이용권은 매달 1일부터 시작한다.        (11월, 12월에도 3달 이용권을 사용할 수 있다 / 다음 해의 이용권만을 구매할 수 있기 때문에 3달 이용권은 11월, 12월, 1윌 이나 12월, 1월, 2월 동안 사용하도록 구매할 수는 없다.)    ④ 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       10 40 100 300    0 0 2 9 1 5 0 0 0 0 0 0 10 100 50 300    0 0 0 0 0 0 0 0 6 2 7 8 …	#1 110 #2 100 #3 400 #4 530 #5 430 #6 1080 #7 1840 #8 800 #9 1980 #10 2260

---

2. 문제풀이

DP를 이용하여 문제를 해결했다. 1월부터 12월까지 돌면서 계산을 하는데 매달 매달 가장 적은 비용을 리스트에 적어서 이용하는 방식이다. 계산방식은 1. 이전달 + 이번달 전부다 일권사용했을때, 2. 이전달 + 이번달 1달권 사용했을때, 3. n이 3보다 크다면 3달전 비용 + 3달권 비용 4. n이 12라면 1년권 으로 계산하여 가장 적은비용을 갱신하는 방식이다.

---

3. 소스코드

# 1952 수영장
 
T = int(input())
for t in range(1, T+1):
    #일, 1달, 3달, 1년 이용권
    price_list = list(map(int, input().split()))
    #월별 이용날
    month_list = list(map(int, input().split()))
    #결과 저장 변수 그 달의 최저값을 저장한다.
    result_list = [0] * 13
    for n in range(1, 13):
        #가격을 저장할 임시변수
        a = [0, 0, 987654321, 987654321]
        #일권으로 계산했을때, 전달비용 + 참여일수 * 일비
        a[0] = result_list[n-1] + month_list[n-1] * price_list[0]
        #1달권으로 계산했을때, 전달비용 + 1달권 비용
        a[1] = result_list[n-1] + price_list[1]
        #3달권으로 계산했을때, 3달 전비용 + 3달권비용
        if n >= 3:   a[2] = result_list[n-3] + price_list[2]
        #1년권으로 계산했을때, 1년비용
        if n >= 12:   a[3] = price_list[3]
        #현시점에서 제일 적은 비용의 값을 넣는다.
        result_list[n] = min(a)
    print('#{} {}'.format(t, result_list[12]))