STUDY/Algorithm

[SWEA] 1952 수영장

sinawi95 2021. 3. 14. 22:00
728x90

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

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

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