프로그래머스, 숫자 변환하기

문제 설명

자연수 x를 특정한 계산에 맞춰서 y로 변환하는 최소 값을 구하는 문제이다. 만일 구할 수 없으면 -1을 반환한다.

https://school.programmers.co.kr/learn/courses/30/lessons/154538?language=java 

프로그래머스

문제 풀이

문제를 보자마자 dp가 생각났다. 백준에도 비슷한 문제가 있었던 거 같은데.
https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

dp로 풀기 위해서는 제일 먼저 탑 다운으로 풀 건지, 바텀 업으로 풀 건지 정해야 한다.

첫 번째 접근

처음에는 바텀 업으로 풀려고 했다. 제일 빠른 접근 횟수를 원하니 y에서 x로 가기 위해서는 무조건 작은 수를 만들어야 한다고 생각했다. 나누기를 하면 숫자가 높은 확률로 작아지니 3으로 나누고 안 되면 2로 나누고 둘이 모두 안 된다면 빼기로 조건문을 만들었다.

 

그러나 문제에서 주어진 두 번째 조건 같은 경우는 나누기 보다 빼기를 했을 때 더 빨리 접근한다.

y가 40인데, 2로 나누면 값이 20이지만 30으로 빼면 10이 되서 x에 더 빨리 접근한다.

 

그러므로 잘못된 접근이었다.

두 번째 접근

그래서 바텀 업 방식으로 바꿔서 풀었다.

일단 dp 배열을 하나 만들어 줬다. 그리고 최솟값을 구할 거니까 최댓값을 넣어줬다.

x부터 시작할 거기에 dp[x]는 0으로 만들어 준 다음 반복문을 x부터 y까지 돌리면서 각 숫자 i로 만들 수 있는 수의 최솟값을 구해줬다.

 

            if(i+n <= y){
                dp[i+n] = Math.min(dp[i+n], dp[i]+1);
            }

위의 식을 보면 i에 n을 더해서 y보다 작거나 같은지 확인한다.

그리고 만일 조건문을 만족하면 i+n을 만들 수 있는 최소 횟수를 구해준다.

이러한 방식을 2 곱하기와 3곱하기에도 적용한다.

 

이렇게 하면 dp의 각 숫자에는 주어진 규칙을 이용해서 만들 수 있는 최솟값이 들어가게 된다.

 

반복문을 모두 마친 뒤 dp[y]의 값이 max와 같다면 answer에 -1을 넣고 아니면 dp[y]를 넣어서 반환하면 된다.

코드

python

def solution(x, y, n):
    answer = 0
    maxInt = int(1e9)
    dp = [maxInt for _ in range(y+1)]
    dp[x] = 0
    
    for i in range(x, y):
        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] == maxInt:
        answer = -1
    else:
        answer = dp[y]
        
    return answer

java

class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;
        int[] dp = new int[y+1];
        int max = 1000001;
        
        for(int i=0; i<=y; i++){
            dp[i] = max;
        }
        
        dp[x] = 0;
        
        for(int i=x; i<y; i++){
            if(i+n <= y){
                dp[i+n] = Math.min(dp[i+n], dp[i]+1);
                
            }
            if(i*2 <= y){
                dp[i*2] = Math.min(dp[i*2], dp[i]+1);
            }
            if(i*3 <= y){
                dp[i*3] = Math.min(dp[i*3], dp[i]+1);
            }
        }
        
        
        if(dp[y] == max){
            answer = -1;
        }else{
            answer = dp[y];
        }
        
        return answer;
    }
}