[Baekjoon] 1463 1로 만들기 - JAVA

문제

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

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

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

---

입력

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

---

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

---

예제 입력 1 

2

예제 출력 1 

1

---

예제 입력 2 

10

예제 출력 2 

3

---

힌트

10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.

---

📝 제출 답안

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

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());

        System.out.println(count(n));
    }

    public static int count(int n) {
        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);
            }
        }

        return dp[n];
    }
}

 

DP(다이나믹 프로그래밍)를 사용하여 n을 1로 만들기 위한 최소 연산 횟수를 계산하는 문제였다.

solved.ac 에서 Class3 으로 넘어온 뒤로 DP로 푸는 문제들을 많이 접하고 있는데 이번 문제를 통해서 DP 문제를 제대로 활용할 수 있게 된 것 같다.

 

먼저 입력은 BufferedReader로 정수 n을 입력받는다.

(백준을 풀면서 맨날 시간 제한 문제로 BufferedReader만 사용 중인데 Scanner 까먹을 것 같으니까 scanner로도 풀어봐야겠다..물론 효율 측면에서 BufferedReader 최고!!)

 

문제 풀이를 위한 메모장

 

정수 n을 1로 만드는 최소 연산 횟수 계산을 위해 2부터 12까지 적어보았다.

1은 따로 연산이 필요 없으니까 0으로 고정이고, 이후 정수들을 몇 개 적어보니 규칙을 찾을 수 있었다.

2나 3으로 나누어 떨어지지 않는 수들은 직전 정수의 최소 연산 횟수에 1을 더한 것(자기 자신 n)과 같고,

2와 3으로 나누어 떨어지는 수는 n/2 또는 n/3인 정수의 최소 연산 횟수에 1을 더한 것(자기 자신 n)과 같았다.

 

다이나믹 프로그래밍으로 코드를 짜보면 아래와 같다.

 

먼저 dp[i] 배열을 사용해 i를 1로 만드는 데 필요한 최소 연산 횟수를 저장해준다.

dp[1]은 이미 숫자 1 이기 때문에 추가 연산이 필요없으니 0으로 초기화 해준다.

 

기본적으로 2나 3으로 나누어떨어지지 않는 경우를 고려하여 dp[i] = dp[i-1] + 1; 로 연산 횟수를 설정한다.

그리고 조건문을 통해 정수 i가 2로 나누어떨어질 경우에는 i/2에서 오는 연산 횟수를 고려하고 현재 dp[i] 값과 비교하여 최소값으로 업데이트 해준다.

마찬가지로 조건문을 통해 정수 i가 3으로 나누어떨어질 경우에는 i/3에서 오는 연산 횟수를 고려하고, 현재 dp[i] 값과 비교하여 최소값으로 업데이트 해준다.

 

처음 문제를 풀 때 최소값을 비교해주는 로직을 생각하지 못해서 오류가 떴었다.

2와 3으로 나누는 경우가 모두 가능한 경우에 최소값을 비교해주는 로직을 신경써주어야 했기에

dp[i] = Math.min(dp[i], dp[i / 2] + 1); 로 변경해주었다.

 

시간복잡도를 고려해보자면

for 루프가 2부터 n까지 한 번씩 실행되며 각 루프에서 상수 시간 연산(if문이랑 Math.min)만 수행되므로 총 시간복잡도는 O(n)이다.

 

제출 현황