[SWEA] 1952 수영장

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq&categoryId=AV5PpFQaAQMDFAUq&categoryType=CODE&problemTitle=1952&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

for tc in range(1, int(input()) + 1):
    prices = list(map(int, input().split()))
    months = [0]+list(map(int, input().split()))
    total_price = [0] * 13
    for i in range(1, 13):
        tmp0 = total_price[i - 1] + months[i] * prices[0]
        tmp1 = total_price[i - 1] + prices[1]
        total_price[i] = min(tmp0, tmp1)
        if i < 3: continue
        tmp2 = total_price[i - 3] + prices[2]
        total_price[i] = min(total_price[i], tmp2)
    min_total_price = min(total_price[12],prices[3])
    print("#{} {}".format(tc, min_total_price))

접근한 방법은 1일권, 1개월권, 3개월권, 1년권으로 끊었을때 작은 값을 매월 기록하는 방법으로 했다.

1월에 가는 일수 * 1일권 가격과 1개월권 가격을 비교해서 작은값을 1월에 넣는다.

3월 이후부터는 3월달까지 계산했을때 1일권, 1개월권 중 작은 값과 3개월권도 가격을 비교한다.

12월까지 확인하고 마지막으로 1년권과 비교하면 가장 작은 값이 나오게 된다.

다른 코드를 읽어보니 방식이 DP 인것같다.

---

BFS, DFS, 백트래킹 문제만 보다가 이 문제를 보니 어려웠다. 

다른 유형들도 자주 풀어야겠다.