SWEA 1952 수영장 (파이썬)

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

SW Expert Academy

 

---

풀이

def solve(index, cost):
    global rst
    if cost > rst: return
    if index >= 12:
        rst = min(cost, rst)
        return
    if schedule[index]:
        solve(index+1, cost+(schedule[index] * d))
        solve(index+1, cost+m)
        solve(index+3, cost+m3)
        solve(index+12, cost+y)
    else:
        solve(index+1, cost)

for tc in range(int(input())):
    d, m, m3, y = map(int, input().split())
    schedule = list(map(int, input().split()))

    rst = 0xffffffff
    solve(0, 0)
    print(f'#{tc+1}', rst)

 

---

후기 및 해설

• 백트래킹으로 푼 문제이다.
• 다른 풀이들을 보니 반복 또는 dp가 실행시간이 빠르지만, 백트래킹으로 모든 경우의 수를 재귀로 돌리면, 
• 알아서 최소값을 만들어줘서 백트래킹으로 풀었다.
• 1월에서 12월까지 (함수의 index) 증가하면서 모든 경우의 수를 조합해본다.