[코테] 프로그래머스 파이썬 Lv2. 숫자변환하기

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

프로그래머스

 

이때 나눌 수 있는 수는 2와 3이다.

 

처음에는 y값을 x값으로 나눈 몫이 2나 3으로 나눠진다면 if문으로 분리하여, 나머지를 다시 n으로 나눌 수 있다면 정답 후보로 올렸다.

 

또 다른 연산 방식으로 더하기 연산을 할 수 있는 n의 배수를 활용하였다. y값에서 x값을 뺀 값이 n으로 나눠진다면 n만을 이용하여 연산이 가능했기 때문에 이같은 경우도 정답 후보로 추릴 수 있었다.

 

def solution(x, y, n):
    answer = 0
    array=[]
    
    check=y//x
    remain=y%x
    subtract=y-x
    
    
    if check%2==0:
        if remain%n ==0:
            result=remain//n
            result+=check//2
            array.append(result)
            
    if check%3==0:
        if remain%n ==0:
            result=remain//n
            result+=check//3
            array.append(result)
            
    if subtract%n==0:
        result=subtract//n
        array.append(result)
        
        
    if len(array)==0:
        answer=-1
    else:
        answer=min(array)
    return answer

 

 

 

문제는 2와 3을 분기하지 않고 함께 사용하여 연산하는 것을 구현하지 못한 것이다. 이같은 문제를 해결하기 위해, 다이나믹 프로그래밍 활용하는 것이 필요했다.

 

import math

def solution(x, y, n):
    if x == y:
        return 0
    
    dp = [math.inf]*(y+1)
    dp[x] = 0
    
    for i in range(x, y+1):
        if dp[i] == math.inf:
            continue       
        if y>=i+n:
            dp[i+n] = min(dp[i]+1, dp[i+n])
        if y>=i*2:
            dp[i*2] = min(dp[i]+1, dp[i*2])
        if y>=i*3:
            dp[i*3] = min(dp[i]+1, dp[i*3])
    
    return dp[y] if dp[y]!=math.inf else -1