[programmers] Lv2 숫자 변환하기 - Python

코딩테스트 연습 - 숫자 변환하기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

 

 

<문제 풀이>

- Dynamic Programming 중 Memoization을 이용한 풀이

- 초기 값(횟수)을 넣어주고 dp 테이블 생성 후 for문으로 탐색

- 이때 생성되지 않는 값은 pass

- 주어진 조건으로 연산된 값이 되는 index에서의 연산 횟수와 연산 전 값에서 연산 횟수 +1 중 최솟값을 갱신하는 방식으로 진행

    → dp[idx+n] = min(dp[idx+n], dp[idx]+1)

 

 

 

<Code>

def solution(x, y, n):
    dp = [9876543210] * (y+1)    # dp 테이블(최소 카운트 누적)
    dp[x] = 0    # x는 카운트 0

    for idx in range(x, y+1):    # x값 이후 부터 체크
        if dp[idx] == 9876543210:    # 값이 만들어지지 않는 부분은 pass
            continue

        # idx가 y 보다 커지지 않도록 체크 & 문제에서 주어진 케이스 마다 카운트 체크
        if idx + n <= y:
            dp[idx+n] = min(dp[idx+n], dp[idx]+1)

        if idx * 2 <= y:
            dp[idx*2] = min(dp[idx*2], dp[idx] + 1)

        if idx * 3 <= y:
            dp[idx*3] = min(dp[idx*3], dp[idx] + 1)

    if dp[y] == 9876543210:    # y가 불가능한 경우 -1 리턴
        return -1
    else:
        return dp[y]

※ 잘못된 점, 개선점 등이 있다면 언제든 댓글로 알려주시면 감사하겠습니다.