문제 - 숫자 변환하기

문제 접근

1. bfs를 이용하여 풀이방법
   • 방문처리를 위해 hashset을 이용한다. (set.contains()은 O(1)이므로)
   • queue에 x + n, x 2 , x 3을 넣어주면서 y값이 될때에 횟수를 출력

import java.util.*;

class Solution {
    int answer;
    public int solution(int x, int y, int n) {
        answer = -1;
        
        bfs(x,y,n);
        return answer;
    }
    
    public void bfs(int start,int end, int n)
    {
        Queue <int []> q = new LinkedList<>();
        q.offer(new int[]{start,0});
        
        Set<Integer> visited = new HashSet<>();
        visited.add(start);
        
        while(!q.isEmpty())
        {
            int cnt[] = q.poll();
            
            if(cnt[0] == end)
            {
                answer = cnt[1];
                return;
            }
            
            if(cnt[0] + n <= end && !visited.contains(cnt[0] + n))
            {
                q.offer(new int []{cnt[0]+n,cnt[1]+1});
                visited.add(cnt[0]+n);
            }
            
            if(cnt[0] * 2 <= end && !visited.contains(cnt[0] * 2))
            {
                q.offer(new int []{cnt[0] * 2,cnt[1]+1});
                visited.add(cnt[0] * 2);
            }
            
            if(cnt[0] * 3 <= end && !visited.contains(cnt[0] * 3))
            {
                q.offer(new int []{cnt[0] * 3,cnt[1]+1});
                visited.add(cnt[0] * 3);
            }
            
        }
    }
}

2. dp를 이용하여 풀이방법
   • x ~ y까지 탐색하면서 +n, 2, 3을 한다.
   • 변환하는 값이 y보다 작거나 같으면 dp[i]+1과 dp[변환하는 값]을 비교하여 더 작은 횟수를 저장

import java.util.*;

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