728x90
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, 백트래킹 문제만 보다가 이 문제를 보니 어려웠다.
다른 유형들도 자주 풀어야겠다.
'STUDY > Algorithm' 카테고리의 다른 글
[SWEA] 4013 특이한자석 (0) | 2021.03.16 |
---|---|
[백준] 12100. 2048(Easy) (0) | 2021.03.16 |
[SWEA] 10966 물놀이를 가자 (0) | 2021.03.14 |
[SWEA] 1953 탈주범 검거 (0) | 2021.03.14 |
[SWEA] 1949 등산로 조성, 모의 SW 역량테스트, python (0) | 2021.03.11 |