[모의 SW 역량테스트] 수영장

SWEA 문제 모음: https://swexpertacademy.com/main/code/problem/problemList.do

SW Expert Academy

DP로 풀 수 있는 문제다. 검색을 좀 해보니 DFS로도 풀 수 있다는 글이 있던데, 나는 잘 모르겠다.

 

현재 구해야 하는 m월 이전에 구한 결과들(1~m-1월)이 optimal이라고 하고, 현재 상황에서 고를 수 있는 3가지 중 최저 비용을 구해 sol[m]에 저장한다. 가장 마지막에는 1년 이용권을 끊는 것이 좋은지까지 비교해서 출력하면 된다.

 

	t = int(input())
	for t_idx in range(1, t+1):
	voucher = list(map(int, input().split()))
	month = [0]+list(map(int, input().split()))
	sol = [0]*13 # DP 정답 저장용
	sol[1] = min(month[1]*voucher[0], voucher[1]) # 처음 1개월 최소 사용 비용
	sol[2] = sol[1] + min(month[2]*voucher[0], voucher[1]) # 처음 2개월 최소 사용 비용
	for m in range(3, 13): # 매 월마다
	sol[m] = min(sol[m-3]+voucher[2], sol[m-1]+month[m]*voucher[0], sol[m-1]+voucher[1])
	# m-3개월 최소 비용 + 3개월 이용권 // m-1개월 최소 비용 + m월 1일 이용권 // m-1개월 최소 비용 + m월 1개월 이용권
	# 최솟값을 저장
	print("#{} {}".format(t_idx, min(sol[-1], voucher[-1])))

view raw 수영장.py hosted with ❤ by GitHub