BOJ_1463 : 1로 만들기

👉 문제링크

1463번: 1로 만들기

---

---

🔸 문제 분석 🔸

• 정수 N을 1로 만드는 가장 적은 연산 수를 출력한다.
  • 연산은 -1, /3, /2 세 가지가 있다.
• DP, DFS, BFS 모두 풀이 가능하다.

---

🔸 DP 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        // DP
        int[] dp = new int[N+1];
        dp[1] = 0;
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i-1];
            if (i % 2 == 0) dp[i] = Math.min(dp[i], dp[i/2]);
            if (i % 3 == 0) dp[i] = Math.min(dp[i], dp[i/3]);
            dp[i]++;
        }

        // Output
        System.out.print(dp[N]);
    }
}

🔸 코드 해석 🔸

• dp[n]은 n을 만드는 최소 연산 횟수이다.
  • N까지 반복하며 계산 값을 누적해간다.
  • 세 연산의 결과값 중 최소값 + 1 을 현재 위치에 저장한다.

---

🔸 DFS 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    private static int MIN = Integer.MAX_VALUE;
    private static void dfs(int d, int n) {
        if (MIN < d) return;
        if (n == 1) {
            MIN = Math.min(MIN, d);
            return;
        }
        if (n%3 == 0) dfs(d+1, n/3);
        if (n%2 == 0) dfs(d+1, n/2);
        dfs(d+1, n-1);
    }

    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        // DFS
        dfs(0, N);

        // Output
        System.out.print(MIN);
    }
}

🔸 코드 해석 🔸

• 재귀 메서드 dfs에서 3가지 연산을 1에 도달 할 때 까지 수행한다.
  • 도달 했을 때의 깊이를 MIN에 저장한다.
  • 재귀 깊이가 MIN보다 깊어 지는 경우는 볼 필요가 없으므로 백트래킹으로 사용한다.

---

🔸 BFS 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    private static class Pair {
        int n, d;
        public Pair(int n, int d) {
            this.n = n;
            this.d = d;
        }
    }
    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        // BFS
        Queue<Pair> queue = new LinkedList<>();
        boolean[] visit = new boolean[N+1];

        queue.add(new Pair(N,0));

        int cnt = 0;
        while (!queue.isEmpty()) {
            Pair pair = queue.poll();

            if (pair.n == 1) {
                cnt = pair.d;
                break;
            }

            if (!visit[pair.n]) {
                visit[pair.n] = true;

                if (pair.n%3 == 0) queue.add(new Pair(pair.n/3, pair.d+1));
                if (pair.n%2 == 0) queue.add(new Pair(pair.n/2, pair.d+1));
                queue.add(new Pair(pair.n - 1, pair.d+1));
            }
        }

        // Output
        System.out.print(cnt);
    }
}

🔸 코드 해석 🔸

• 3가지 연산의 결과를 큐에 반복적으로 넣는다.
• 최초로 1에 도착한 순간이 가장 빠른 경우이므로 그때의 깊이를 출력한다.

---

🔸 end 🔸

• 원래 DP 연습을 위한 문제지만, 조건이 너무 타이트하진 않아서 DFS와 BFS로 풀이가 가능하다.
  • 단, DFS의 경우 백트래킹이 필요하다.
• 문제 분석과 풀이 계획을 적어가며 풀이했다.