SW Expert Academy - 수영장 (python)

❓ 문제 - SW Expert Academy - 수영장  python 풀이법

 

출처 

(https://swexpertacademy.com/main/solvingProblem/solvingProblem.do)

SW Expert Academy

 

 

 

📝 문제해결법

1. 이 문제는 완전탐색(DFS)로 풀었다.

• dfs를 돌려 1월달 부터 모든 경우의 수를 탐색한다.
• 일단 이용금액의 최대 금액은 1년권이므로 최솟값을 갱신시킬 처음 값을 1년권의 금액으로 잡는다.
• dfs를 계속 돌려 13월은 1년을 넘으므로 m-1월까지 이용했던 금액과 최솟값을 찾을 값을 비교해서 갱신한다.
• m월부터 1일권, 한달권, 3개월권을 끊을 경우로 모두 탐색하여 계속 DFS를 돌린다.

2. 문제 풀면서 느낀점

• 1년권을 고려할 필요가 없음. 그냥 최대값으로 잡으면 됨
• 만약 이번달을 이용을 안해도 1일권, 한달권, 3개월권 모두 고려해서 탐색에 넣는다.

 

💻 소스코드

T = int(input())

def dfs(m, cash):
    global min_money
    if m >= 13:
        min_money = min(min_money, cash)
        return
    else:
        dfs(m+1, cash+money[0]*month[m])
        dfs(m+1, cash+money[1])
        dfs(m+3, cash+money[2])

for test_case in range(1, T+1):
    money = list(map(int, input().split()))
    month = [0] + list(map(int, input().split()))
    min_money = money[3]
    dfs(1, 0)

    print(f'#{test_case} {min_money}')