[SWEA][D4][#01952] 수영장

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

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

김 프로는 지출이 너무 많아 내년 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]의 형태로 수립된다.

Table 1 생략

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

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

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

제약 사항

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

My Sol

def use(now, ssum):
    if now >= max_m:
        global min_cost
        min_cost = min(min_cost, ssum)
        return

    if not months[now]:
        use(now+1, ssum)
        return

    # 일/월 이용
    day = months[now]*DC
    mon = MC
    val = day if day < mon else mon
    use(now+1, ssum + val)

    # 분기 이용
    use(now+3, ssum + QC)

T = int(input())
for tc in range(1, T+1):
    DC, MC, QC, YC = map(int, input().split())
    months = list(map(int, input().split()))

    min_cost = YC
    max_m = 12
    use(0, 0)

    print(f'#{tc} {min_cost}')

재귀를 사용하였는데, 각 테스트 케이스마다 일, 월, 분기, 연별 금액과 월별 이용일수를 입력받아 저장한다. 기본적으로 연 단위 이용권을 구매하면 1번으로 구매를 마칠 수 있기 때문에 이 금액을 베이스로 둔다. 그리고 재귀함수를 작성해주는데, 기본적으로 필요한 depth에 대한 인자는 now로, 현재 월수를 의미한다. 이는 재귀를 타면서 한 달에 대한 계산값과 함께 1을 더해 재호출한다. 일별 금액과 이용 일수를 곱한 값이 월정액보다 많은지 적은지를 판단해 다음 달을 조회할 때 금액 합산을 넘겨주는 인자를 포함한다.

분기 이용권을 구매하면 그 사이 3달의 이용은 고려하지 않아도 되기 때문에 depth에 3을 더해 전달해준다. 물론 이용액 합산 인자에 분기 금액을 더해 전달한다.

만약 한 달동안 수영장을 가지 않는 달이 있다면 다음 달로 넘어간다.

depth가 12보다 크거나 같다면 현재까지 오는데 필요했던 합산 금액과 global의 min_cost와 비교해 작은 값을 min_cost에 갱신해주면 된다.

결과

PASS

보다 더 효율적인 로직이 있을 것 같다. 고민해보자.