SWEA-1952-수영장

1일, 1달, 3달, 1년의 이용권을 적절히 사용하여 수영장 이용자가 계획한 계획표에 맞게 최소 비용을 구하는 문제

• 최적해를 구하는 문제 -> 주로 완전탐색을 해야함
• 재귀를 사용한 DFS로 가능한 모든 비용을 확인하고 그 중에서 최소 비용을 구한다.
• 필요없는 탐색은 최소화한다.

def dfs(month, cost): # DFS를 이용한 완전탐색
    global ans # 글로벌 변수로 ans 설정

    if ans <= cost: # 최솟값으로 구한 ans 보다 현재까지 더한 값이 더 크면 더이상 쓸모가 없으므로 return
        return

    if month > 11: # 11보다 month가 크면(3달권의 경우 11보다 커져버릴 수 있음) 현재까지의 최솟값을 구했으므로 ans에 할당 후 return
        ans = cost
        return

    # 수영장을 방문한 달
    if P[month]:
        dfs(month+1, cost + (P[month] * D))
        dfs(month+1, cost + M)
        dfs(month+3, cost + Q)
    # 수영장을 방문하지 않은 달
    else:
        dfs(month+1, cost)


for T in range(1, int(input())+1):
    D, M, Q, Y = list(map(int, input().split())) # 1일권 1달권 3달권 1년권
    P = list(map(int, input().split())) # 사용자의 계획표
    ans = Y # 최소값을 저장할 변수, 1년권을 기준으로 잡고 최소값을 구한다
    dfs(0, 0) # 0~11 즉 12달에 걸쳐 가능한 모든 비용을 구하고 그 중 최솟값을 해로 정한다.
    print('#{} {}'.format(T, ans))