SWEA 1952번 파이썬 문제풀이(수영장)

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

SW Expert Academy

 

---

해당 문제 처음에는 일반적인 구현문제인줄 알았으나 풀다보니 dfs라는것을 알게 되었다. 

전체 풀이방식은 다음과 같다.

 

1. 각 달마다 일 가격 * 수영장에 가야하는 해당 달의 일수 와 달가격중 싼것을 저장해준다.

2. 1에서 구해진 값들을 기준으로 한달가격으로 적용하거나 일부 달을 3달가격으로 적용하는 것 중 어떤 값이 모든 경우를 계산하여 어느 값이 더 적은지 구해준다.(dfs를 이용)

3. 2에서 구해진 값과 년가격 중 싼 값을 구해준다.

 

이렇게 3가지 방식으로 구현하여야 한다. 자세한 설명은 주석을 달아 놨다.

import sys

sys.stdin = open('input.txt', 'r')


def dfs(month, cost):
    global result
    # 12월에서 3달비용을 이용하는 경우도 1달밖에 이용하지 못하지만 3달비용이 나오므로
    # 최대 15까지 month값이 정해진다.
    if 13 <= month <= 15:
        if cost < result:  # 만약 현재 저장된 값보다 값이 적다면
            result = cost  # 그 값을 현재 값으로 바꿔준다.
        return

    dfs(month + 1, cost + one_cost[month])  # 현재 비용 + 다음달 비용
    dfs(month + 3, cost + three_m)  # 현재비용 + 3달비용


T = int(input())

for tc in range(1, T + 1):
    day, m, three_m, y = map(int, input().split())

    plan = [0] + list(map(int, input().split()))
    one_cost = [0]  # 한달 단위로 최저가 구하기(일가격과 한달중 적은 가격을 구해준다.)
    for i in range(1, 13):  # 1월부터 12월 까지 돌면서
        if plan[i] * day > m:  # 만약 계획일 * 일가격 보다 한달 가격이 더싸다면
            one_cost.append(m)  # 한달가격을 적용시킨다.
        else:  # 반대라면
            one_cost.append(plan[i] * day)  # 그 값을 적용

    result = 1 << 60  # 결과를 출력할 변수
    dfs(1, 0)  # 1월부터 dfs를 돈다.(한달과 3달중 적은 가격을 구해준다.)
    if result > y:  # 만약 년가격이 더 싸다면
        result = y  # 년가격을 대입

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