[Python] 프로그래머스 lv2 - 숫자 변환하기

[Python] 프로그래머스 lv2 - 숫자 변환하기

 

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

프로그래머스

 

 

문제 설명

 

설명 및 입출력

• 주어진 숫자를 기준으로 x가 y가 되기까지의 최소 연산 횟수를 구하는 문제이다. 하나의 방법으로는 제한사항, 시간초과, 런타임 에러등의  두 가지의 방법을 생각했었다. 
  • 재귀  - 런타임 에러 발생
    • 문제에서 요구하는 계산을 재귀로 호출, 재귀에서 호출하며 들어오는 cnt를 list에 저장
    • 저장된 list의 최솟값을 answer로 반환
      • 만약에 x==y가 성립되지 않으면 -1을 반환해야 하는 경우 발생
      • 해당 경우는 기존에 값을 하나 리스트에 삽입하고 해당 값이 최솟값이면 -1을 반환하는 방식을 채택
  • DP - 동적 프로그래밍
    • 메모제이션을 활용, 인덱스를 통해 접근하는 방법이다
      • 메모제이션 : 함수 호출의 결과를 저장해서 동일한 계산의 반복을 피하는 방법이다. 
    • Y+1의 크기를 갖는 리스트를 선언, 리스트의 초기값은 1e9로 큰 수로 설정
    • X번째 항목은 0으로 지정하여 시작점을 의미
    • for x부터 y+1까지 반복문 실행
      • 단계별로 i의 값이 계산되면 y보다 큰지 판단
      • 이때 min 메서드를 사용하여 각 리스트의 계산값의 최솟값을 넣어준다
    • return으로 인덱스 y의 값을 불러온다

풀이 코드

 

- 재귀 

def solution(x, y, n):
    
    def recur(x,y,n,cnt,numlist):
        if x==y:
            return numlist.append(cnt)
        elif x>y:
            return 1e9
        else:
            recur(x+n,y,n,cnt+1,numlist)
            recur(x*2,y,n,cnt+1,numlist)
            recur(x*3,y,n,cnt+1,numlist)
    
    numlist=[1e9]
    recur(x,y,n,0,numlist)
    answer = min(numlist)
    if answer == 1e9:
        return -1
    else:
        return answer

 

- DP

def solution(x, y, n):

    dp = [1e9] * (y + 1)
    dp[x] = 0

    for i in range(x, y + 1):
        if dp[i] == 1e9:
            continue

        if i + n <= y:
            dp[i + n] = min(dp[i + n], dp[i] + 1)

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

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

    if dp[y] == 1e9:
        return -1

    return dp[y]