[백준/1463] 1로 만들기 - Java 자바

https://www.acmicpc.net/problem/1463

 

개념: dp, bfs

 

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

 

---

 

1. dp로 푼 풀이

주어진 예시로 생각해보면 `dp[10] = min(dp[3] + 1, dp[5] + 1, dp[9] + 1)`이다.

d[n]을 구하고자 할때 n-1은 항상 가능하므로 dp[n] = dp[n-1] + 1을 구한다. 그리고 n이 3으로 나누어지면 min(dp[n], dp[n/3]+1)으로 값을 업데이트한다. n이 2로 나누어질 때도 마찬가지다. 

import java.io.*;
import java.util.*;

public class baekjoon {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N+1];
        dp[1] = 0;
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i-1] + 1;
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i/2] + 1);
            }
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i/3] + 1);
            }
        }
        System.out.println(dp[N]);
    }
}

 

 

2. bfs로 푼 풀이

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        Queue<Integer> queue = new LinkedList<>();
        int[] visited = new int[N+1];
        
        queue.add(N);
        visited[N] = 1;

        while (!queue.isEmpty()) {
            int current = queue.poll();

            if (current == 1) {
                System.out.println(visited[current] - 1);
                return;
            }

            if (current % 3 == 0 && visited[current / 3] == 0) {
                visited[current / 3] = visited[current] + 1;
                queue.add(current / 3);
            }

            if (current % 2 == 0 && visited[current / 2] == 0) {
                visited[current / 2] = visited[current] + 1;
                queue.add(current / 2);
            }

            if (current - 1 > 0 && visited[current - 1] == 0) {
                visited[current - 1] = visited[current] + 1;
                queue.add(current - 1);
            }
        }
    }
}

 

 

일단 dp가 구현이 더 쉽고, 메모리도 살짝 더 나은 편이다.