[SWEA 코딩] [모의 SW 역량테스트] 수영장 - PYTHON #1952

 

def dfs(idx,price,cnt): # 인덱스 값, 현재 가격, 몇 달 계산했는지
    global min_price # min_price 값을 변경해야 하므로 global

    if price >= min_price: # 가지치기 1. 최소 값이 현재 값보다 크면 더 작아질 수 없음 
        return

    if idx >= 12: # 탈출 조건
        if cnt == swim_cnt: # cnt와 swim_cnt 비교 == 수영하는 달을 체크 했는지 확인하는 것
            if min_price > price: # 현재 가격이 최소 가격보다 작으면
                min_price = price # 바꾸기
        return

    for q in range(idx,12): # idx 값이 시작점(바로 직전 dfs에서 idx 이 전까지 확인했기 때문)
        if schedule[q] != 0: # 수영하는 달이면
            dfs(q+1,price+(swim_price[0]*schedule[q]),cnt+1) # 1일
            dfs(q+1,price+swim_price[1],cnt+1) # 1개월
			# 1일과 1달은 모두 수영하는 날이 1일이라도 있어야 결제 가능
            
        if q < 10: # 3개월 
            if schedule[q] != 0 or schedule[q+1] != 0 or schedule[q+2] != 0:
                # 연속된 3개월 중에 한 달이라도 수영하는 날이 없으면 결제할 필요 없음
                
                q_cnt = 0
                # 1개월만 수영하기 위해서 3개월짜리 이용권 구매 가능
                # 그래서 q_cnt를 지정해서 필요한 값을 더해준다
                
                for e in range(3):
                    if schedule[q+e] != 0:
                        q_cnt += 1
                dfs(q+3,price+swim_price[2],cnt+q_cnt)
				
    if cnt == swim_cnt: # 탈출 조건 2
        if min_price > price:
            min_price = price
    return

T = int(input())

for tc in range(1,1+T):
    swim_price = list(map(int,input().split())) # 1일, 1달, 3달, 1년

    schedule = list(map(int,input().split())) # 수영 스케쥴

    min_price = swim_price[3] # 현재 최소 가격은 1년짜리 이용권 구매한 경우

    swim_cnt = 0 # 몇 개월 수영하는지 확인하기 위함
    for w in schedule:
        if w != 0:
            swim_cnt += 1

    dfs(0,0,0)

    print('#{} {}'.format(tc, min_price))

내가 작성한 코드에서 cnt값이 필요한 이유는 다음과 같다

 

예를 들어, 10,11,12 수영 스케쥴이 있는 경우, dfs가 처음 한 바퀴를 돌고 return을 하면 10, 11월 - 1일권, 12월 - 1개월이 된다.

 

여기서 다시 return을 하면 10,11 - 1일권, 12월 - 3개월 권을 구매해야 하는데, 조건이 충족하지 않기 때문에 그냥 넘어가게 된다.

 

이 상황에서의 금액은 12월 한 달 간의 수영 스케쥴이 제외된 금액이기 때문에 최소 금액보다 작아질 가능성이 있다.

 

그래서 이 상황을 배제하기 위해 cnt 값과 siwm_cnt값을 집어 넣어 비교한 것이다.

 

또한, 이 문제에서 가장 많은 시간을 잡아먹은 것이 테스트케이스 2번이었다...

 

이는 연속된 3개월 == 3개월 모두 수영 스케쥴이 존재해야 함 으로 잘못 이해했기 때문이었음 ㅠㅠ

 

암튼 문제를 좀 더 집중해서 읽고 이해할 필요성을 느꼈다.

 

ps. 개인적인 문제 풀이 방법과 작성한 이유를 적은 것이기 때문에

 

오류나 적절치 않은 문법이 존재할 수 있습니다.

 

혹시 문제를 발견하신 후에 댓글로 남겨주시면 감사한 마음으로 배우고 수정하겠습니다.