[알고리즘] 1로 만들기(백준1463번)_실버3_DP

문제링크

📝 문제

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

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

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

입력

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

출력

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

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

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

        // 0부터 N까지 대입하기 위해 N + 1을 해주었다.
        int dp[] = new int[N + 1];  

        // 0과 1은 0으로 초기화를 하여준다.
        dp[0] = dp[1] = 0;  
        for (int i = 2; i <= N; i++) {  
            if (i % 6 == 0) dp[i] = Math.min(dp[i - 1] + 1, Math.min(dp[i / 2] + 1, dp[i / 3] + 1));  
            else if (i % 2 == 0) dp[i] = Math.min(dp[i - 1] + 1, dp[i / 2] + 1);  
            else if (i % 3 == 0) dp[i] = Math.min(dp[i - 1] + 1, dp[i / 3] + 1);  
            else dp[i] = dp[i - 1] + 1;  
        }  
        System.out.println(dp[N]);  
    }  
}

• 처음에는 경우의 수를 고려해서 규칙을 찾고 조건문으로 풀려고 하였으나 너무 풀리지가 않아서 찾아보니 DP 문제라고 하여 공부하고 풀어보았다.
• 애초에 경우의 수로 구할 수 있는 범위가 아니었다ㅠㅠ
• DP 링크 걸기
• N = 10이라고 하면, 10부터 1까지 내려가면서 최소 연산횟수를 구할 수도 있지만, 1부터 10까지 올라가면서 구하는 방법도 가능하므로 Bottom-up방식으로 구하였다.
• i = 1, 연산이 필요없으므로 0으로 초기화

i	1	2	3	4	5	6	7	8	9	10
연산횟수	0

• i = 2, i가 2로 나누어 떨어질 때는 i / 2 일 경우와 i - 1 을 했을 경우 2가지 연산에 대해 최소 연산횟수를 구해야 한다.
• dp[2 / 2] = dp[1] = 0, dp[2 - 1] = dp[1] = 0 이다. 이 때, 연산을 한 번 하였으므로 +1을 해주면, 나누었을 경우와 뺐을 경우 모두 연산횟수는 1이 된다.

i	1	2	3	4	5	6	7	8	9	10
연산횟수	0	1

• i = 3일 경우도 동일

i	1	2	3	4	5	6	7	8	9	10
연산횟수	0	1	1

• i = 4, i가 2로 나누어 떨어지므로 i = 2일 때와 마찬가지로 계산해본다.
• dp[4 / 2] = dp[2] = 1, 연산횟수 +1을 해서 dp[4] = 2가 되고
• dp [4 - 1] = dp[3] = 1, 연산횟수 +1을 해서 dp[4] = 2, 이 때도 어느 경우든 최소 연산횟수는 2가 된다.

i	1	2	3	4	5	6	7	8	9	10
연산횟수	0	1	1	2

• i = 5, i가 2나 3으로 나누어떨어지지 않으므로 빼기 연산만 한다.
• dp[5 - 1] = dp[4] = 2, 연산횟수 +1을 해서 dp[5] = 3

i	1	2	3	4	5	6	7	8	9	10
연산횟수	0	1	1	2	3

• i = 6, i가 2와 3으로 나누어떨어지므로 세가지 연산을 모두 계산한다.
• dp[6 / 2] = dp[3] = 1, 연산횟수 +1을 해서 dp[6] = 2
• dp[6 / 3] = dp[2] = 1, 연산횟수 +1을 해서 dp[6] = 2
• dp[6 - 1] = dp[5] = 3, 연산횟수 +1을 해서 dp[6] = 4
• 따라서 최소 연산횟수는 2가 된다.

i	1	2	3	4	5	6	7	8	9	10
연산횟수	0	1	1	2	3	2

• 이런식으로 접근하면 아래와 같은 표가 나온다.

i	1	2	3	4	5	6	7	8	9	10
연산횟수	0	1	1	2	3	2	3	3	2	3