프로그래머스 [Lv. 3] 카운트 다운 {언어 : Python} [다시 풀어 보기] [반례]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/131129

프로그래머스

정답 코드

def solution(target):
    visited = [[100001, 0] for _ in range(target+1)]
    def memoryCnt(value, cnt_all, cnt_sb):
        memo_cnt_all, memo_cnt_sb = visited[value]
        if memo_cnt_all > cnt_all:
            visited[value][0] = cnt_all
            visited[value][1] = cnt_sb
            return True
        elif memo_cnt_all == cnt_all:
            if memo_cnt_sb < cnt_sb:
                visited[value][1] = cnt_sb
                return True
        return False
    
    middle = [] # 21 ~ 49
    last = [] # 51 ~ 60
    for i in range(1, 4):
        for j in range(1, 21):
            tmp = i * j
            if tmp > 50:
                last.append(tmp)
            elif tmp > 20:
                middle.append(tmp)
    middle = sorted(list(set(middle)))
    last = sorted(list(set(last)))
    stack = [[target, 0, 0]]
    while stack:
        value, count_all, count_sb = stack.pop()
        if value >= 50:
            if value % 50 == 0:
                memoryCnt(0, count_all+value//50, count_sb+value//50)
            else:
                if memoryCnt(value-50, count_all+1, count_sb+1):
                    stack.append([value-50, count_all+1, count_sb+1])
            for l in last:
                if value < l:
                    break   
                if value % l == 0:
                    memoryCnt(0, count_all+value//l, count_sb)
                    break
                else:
                    if memoryCnt(value-l, count_all+1, count_sb):
                        stack.append([value-l, count_all+1, count_sb])
        elif value >= 20:
            for m in middle:
                if value < m:
                    break
                if value % m == 0:
                    memoryCnt(0, count_all+value//m, count_sb)
                    break
                else:
                    if memoryCnt(value-m, count_all+1, count_sb):
                        stack.append([value-m, count_all+1, count_sb])
            if value % 20 == 0:
                memoryCnt(0, count_all+value//20, count_sb+value//20)
            else:
                if memoryCnt(value-20, count_all+1, count_sb+1):
                    stack.append([value-20, count_all+1, count_sb+1])
        elif value > 0:
            memoryCnt(0, count_all+1, count_sb+1)
        else:
            memoryCnt(0, count_all, count_sb)
    
    answer = visited[0]
    return answer

풀이 방법

1. 초기화
   • visited 배열을 생성하여 각 점수에 대해 최소 다트 수와 '싱글' 또는 '불' 점수 횟수를 저장한다. 초기 값은 [100001, 0]으로 설정한다.
2. 점수 리스트 생성
   • middle: 21에서 49까지의 점수 목록
   • last: 51에서 60까지의 점수 목록
   • 각 점수는 싱글, 더블, 트리플로 확장된다.
3. DFS 탐색
   • stack을 사용하여 목표 점수부터 시작하여 가능한 모든 점수를 탐색한다.
   • 현재 점수 value, 다트 던진 횟수 count_all, '싱글' 또는 '불' 점수 횟수 count_sb를 추적한다.
4. 점수 갱신 및 상태 전이
   • memoryCnt 함수는 visited 배열을 갱신하여 현재 점수가 더 나은 결과인 경우 업데이트한다.
   • 점수가 50 이상일 때, 20 이상일 때, 20 이하일 때 각각의 경우에 대해 가능한 점수를 빼면서 상태를 갱신한다.
   • value가 0이 되면 종료 조건으로 결과를 업데이트한다.
5. 결과 반환
   • visited 배열에서 목표 점수 0에 대한 최적의 다트 수와 '싱글' 또는 '불' 점수 횟수를 반환한다.

느낀점

• 결국 답 안보고 풀었지만 너무 오래 걸렸다...
• 흔히 알려진 코드로 코드 돌려봤는데 내가 조금(?) 더 빠르다.

 내 코드로 돌렸을 때 

내 코드

 

 다른 사람 코드로 돌렸을 때 

다른 사람 코드

반례

• 173 => 50, 50, 60, 13 => [4, 3]
• 100000 => [1667, 2]
• 70 => [2, 2]
• 29 => [2, 2]