SWEA-1952-수영장
1일, 1달, 3달, 1년의 이용권을 적절히 사용하여 수영장 이용자가 계획한 계획표에 맞게 최소 비용을 구하는 문제
- 최적해를 구하는 문제 -> 주로 완전탐색을 해야함
- 재귀를 사용한 DFS로 가능한 모든 비용을 확인하고 그 중에서 최소 비용을 구한다.
- 필요없는 탐색은 최소화한다.
def dfs(month, cost): # DFS를 이용한 완전탐색
global ans # 글로벌 변수로 ans 설정
if ans <= cost: # 최솟값으로 구한 ans 보다 현재까지 더한 값이 더 크면 더이상 쓸모가 없으므로 return
return
if month > 11: # 11보다 month가 크면(3달권의 경우 11보다 커져버릴 수 있음) 현재까지의 최솟값을 구했으므로 ans에 할당 후 return
ans = cost
return
# 수영장을 방문한 달
if P[month]:
dfs(month+1, cost + (P[month] * D))
dfs(month+1, cost + M)
dfs(month+3, cost + Q)
# 수영장을 방문하지 않은 달
else:
dfs(month+1, cost)
for T in range(1, int(input())+1):
D, M, Q, Y = list(map(int, input().split())) # 1일권 1달권 3달권 1년권
P = list(map(int, input().split())) # 사용자의 계획표
ans = Y # 최소값을 저장할 변수, 1년권을 기준으로 잡고 최소값을 구한다
dfs(0, 0) # 0~11 즉 12달에 걸쳐 가능한 모든 비용을 구하고 그 중 최솟값을 해로 정한다.
print('#{} {}'.format(T, ans))
Author And Source
이 문제에 관하여(SWEA-1952-수영장), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@uykgnod/SWEA-1952-수영장저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)