[삼성sw 1952번] 수영장(파이썬)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq&categoryId=AV5PpFQaAQMDFAUq&categoryType=CODE&problemTitle=SW&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2&&&&&&&&& 

SW Expert Academy

어떻게하면 가장 적은 비용으로 구할지

계산하는 문제.

저는 이 문제같은 경우에는

dfs를 활용해서 풀었습니다.

#삼성sw 1952 수영장
def dfs(n,cost):
    global answer
    if cost>=answer:
        return
    if n>=12:
        answer=min(answer,cost)

        return

    #1일치를 끊는 경우
    now_day=plan[n]
    if now_day>0:
        dfs(n+1,cost+now_day*day)
        #1달치를 끊는 경우
        dfs(n+1,cost+month)
    #없으면 그냥 넘김
    else:
        dfs(n+1,cost)
    #3달치를 끊는 경우
    dfs(n+3,cost+three_month)


    return
T=int(input())
for i in range(T):
    day,month,three_month,year=map(int,input().split())
    plan=list(map(int,input().split()))
    #최대는 1년권을 끊는 경우
    answer=year
    dfs(0,0)
    print("#%d %d"%((i+1),answer))

dp를 쓰는 방식이 있는데

dp를 쓰는게 잘 안떠올랐어요.

그래서 dfs로 무식하게 다 탐색하는 방식을 택했습니다.

다만, 시간초과를 줄이고자

현재 answer보다 큰 값이라면

과감하게 날려버리는 식으로 코드를 구성해서

시간초과를 해결했습니다.

https://mungto.tistory.com/254

수영장 Python(SW Expert Academy, SWEA)

이 분 같은 경우에는

정석대로 dp로 문제를 해결하셨습니다.

dp문제가 나오면 까다롭기 때문에

dp로 푸는 방식도 함께 익혀두면 좋을 것 같습니다.