Sw Expert 1952. 수영장 (python)

 

한마디
간만에 맘에 들게 문제 풀어서 올린당ㅎ 문제 푼 시간도, 코딩 길이도, 실행시간도 마음에 든다.

* 문제의 저작권은 Sw expert academy 에 있습니다!

문제 링크는 여기!

SW Expert Academy

각 이용권의 요금과 각 달의 이용 계획이 입력으로 주어질 때, 가장 적은 비용으로 수영장을 이용할 수 있는 방법을 찾고 그 비용을 정답으로 출력하는 프로그램을 작성하라.

 

아이디어

1) 일단 각 달 별로 완전탐색하지 않고 정해줄 수 있는 부분이 있다! (일 이용권을 살 것인지, 달 이용권을 살 것인지!)

2) 그리고 각 달을 한달이용권으로 살 것인지, 세 달 이용권으로 살 것인지 에 따른 완전탐색을 진행해준다.

3) 초기 최소값을 1년 이용권 가격으로 설정하고 비교해준다면, 자연스럽게 1년 이용권에 대한 탐색이 완료된다. 

4) 11월 12월 처리를 해줄 것!

 

#1952 수영장
#code made by pg-wonie

def dfs(exp, idx):
    global min_val
    if idx >= 12:
    #11월과 12월이 세달 이용권을 할 때가 있을 것이기 때문에, 12일때가 아닌 12보다 클 때라고 설정해줌
    #사실 12월은 무조건 세 달이 아닌 한 달혹은 일 이용권을 하는 것이 이득이겠지만 그에 따른 처리를 해주는 것보다
    #이렇게 처리를 해주는 편이 훨씬 간편합니다.
        if min_val > exp:
            min_val = exp
        return
    if month[idx]*ticket[0] < ticket[1]: #한 달을 모두 일 이용권으로 사용하는게 한 달이용권보다 쌀 때
        dfs(exp+month[idx]*ticket[0], idx+1)
    else: # 한달 이용권이 더 쌀 때 
        dfs(exp+ticket[1], idx+1)
    if month[idx]: #만약 그 달에 0일이면 세 달 이용권을 시작하지 않아도 되니까 솎아주기
        dfs(exp+ticket[2], idx+3) #세 달 이용권일 때 idx 처리 주의!


T = int(input())

for test_case in range(1, T+1):
    ticket = list(map(int, input().split()))
    month = list(map(int, input().split()))
    min_val = ticket[3] #일년 이용권을 최소값으로 설정해주기
    dfs(0,0)
    print('#{} {}'.format(test_case, min_val))

바로 통과했고, 시간도 159ms로 아~주 무난했다 ! (물론 C++은 3ms에 조져버리시더라~ 역시 답은 자바씨플인건가!)