SW Expert Academy 1952. [모의 SW 역량테스트] 수영장

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq

SW Expert Academy

완전 탐색을 이용하여 문제를 해결하였다. 나는 BFS를 이용하여 문제를 해결하였다. 하지만 동적 계획법으로도 풀 수 있을 것 같다. 내가 해결한 코드는 다음과 같다.

from collections import deque


def solution(prices, costs):
    answer = prices[-1]
    queue = deque()
    queue.append([0, 0])
    while queue:
        count, sub = queue.popleft()
        if count >= 12:
            if answer > sub:
                answer = sub
        else:
            if costs[count] == 0:
                queue.append([count + 3, sub + prices[2]])
                queue.append([count + 1, sub])
            else:
                queue.append([count + 3, sub + prices[2]])
                if costs[count] * prices[0] < prices[1]:
                    queue.append([count + 1, sub + costs[count] * prices[0]])
                else:
                    queue.append([count + 1, sub + prices[1]])
    return answer


t = int(input())
for test in range(1, t + 1):
    prices = list(map(int, input().split()))
    costs = list(map(int, input().split()))
    ans = solution(prices, costs)
    print('#{} {}'.format(test, ans))