[SWEA] 수영장 (python)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq 

SW Expert Academy

수영장 문제

1일, 1달, 3달, 1년 이용권의 가격으로 달마다 정해진 횟수로 수영장을 이용할 때 비용의 최소값을 구하는 문제

백트래킹이나 다이나믹 프로그래밍(DP)를 이용하면 풀 수 있다.

⚙️내가 푼 정답코드(백트래킹 활용)

# 백트래킹을 이용한 방법
def find(a,pay):
    global result
    if pay >= result:
        return
    if a >= 12:
        result = min(result,pay)
    else :
        find(a+1, pay+plan[a]*d) # 1일권
        find(a+1, pay+m) # 한달권
        find(a+3, pay+m3) # 3달권
        find(a+12, pay+y) # 1년권


T = int(input())
for case in range(1,T+1):
    d, m, m3, y = map(int,input().split())
    plan = list(map(int, input().split()))
    result = float('inf')
    find(0,0)
    print(f'#{case} {result}')

⚙️내가 푼 정답코드(DP 활용)

T = int(input())
for case in range(1, T + 1):
    d, m, m3, y = map(int, input().split())
    plan = list(map(int, input().split()))
    x = [0]*12
    x[0] = min(plan[0]*d, m, m3, y) # 1월
    x[1] = min(x[0] + plan[1]*d, x[0] + m, m3, y) #2월
    x[2] = min(x[1] + plan[2]*d, x[1] + m, m3, y) #3월
    for i in range(3,12):
        x[i] = min(x[i-1] + plan[i]*d, x[i-1] + m, x[i-3] + m3, y) #나머지
    print(f'#{case} {x[11]}')

📌문제 접근 포인트

1. 이용권의 가격과 달마다 이용 횟수가 주어지고, 각각의 케이스 중 비교하면서 최소값을 찾아야 하는 문제이다.
2. 각각의 케이스의 최소값을 구하는 문제이므로 DP를 활용할 수도 백트래킹을 활용할 수도 있다. (시간은 DP가 빠르다)
3. DP를 이용할 경우, 1월, 2월, 3월의 케이스를 구해준 후, 이 후부터는 for문을 이용하여 케이스를 정해주면 된다.
4. 백트래킹을 이용할 경우 12월까지 도달했을 때의 최소값을 구하도록 4개의 케이스를 넣어 비교하게 만들어 주면된다.