백준 1463번 1로 만들기(java) - 다이나믹 프로그래밍, bfs

---

정수 N 이 0일 때와 1일 때 연산 횟수는 0회이므로

dp[0] = dp[1] = 0

이고 N = 2 일 때부터는 N에 -1했을 때, / 3 했을 때, / 2 했을 때를 모두 실행하여 가장 작은 값을 dp[n]에 넣어주면 된다. 즉, dp[n] = dp[n-1] + 1 or dp[n / 3] +1 or dp[n / 2] + 1이다. 이 때 1을 더해주는 이유는 -1 이나 / 3 이나 /2 연산을 한 번 실행했기 때문이다.

 

import java.util.Scanner;

public class Test {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 0;
        for(int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
            if(i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
            if(i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            }
        }
        System.out.println(dp[n]);
        scanner.close();
    }
}

---

+ ) 풀이 추가 - bfs

bfs를 활용해서 n에 대해 2로 나누기, 3으로 나누기, -1 빼기를 모두 수행해서 queue에 넣는다. 

bfs 수행 후 수가 1이 되면 연산 횟수를 출력한다(bfs 이므로 가장 먼저 1이 되는 경우가 가장 최소의 연산 횟수를 갖는 경우이다)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Info {
    int num;
    int cnt;
    Info (int num, int cnt) {
        this.num = num;
        this.cnt = cnt;
    }
}
public class Main {
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        boolean[] visited = new boolean[n+1];
        Queue<Info> que = new LinkedList<>();
        que.offer(new Info(n, 0));
        visited[n] = true;
        while (!que.isEmpty()) {
            Info now = que.poll();
            if (now.num == 1) {
                System.out.println(now.cnt);
                System.exit(0);
            }
            if (now.num % 3 == 0 && !visited[now.num / 3]) {
                visited[now.num / 3] = true;
                que.offer(new Info(now.num/3, now.cnt+1));
            }
            if (now.num % 2 == 0 && !visited[now.num / 2]) {
                visited[now.num/2] = true;
                que.offer(new Info(now.num / 2, now.cnt+1));
            }
            if (!visited[now.num - 1]) {
                visited[now.num - 1] = true;
                que.offer(new Info(now.num - 1, now.cnt+1));
            }
        }
    }
}