[백준] 1로 만들기 (★) (1463번 JAVA) / 400 - 다이나믹 프로그래밍 1

[백준] 1로 만들기 (!) (1463번 JAVA) / 400 - 다이나믹 프로그래밍 1

---

[접근 방법]

 

N의 경우를 4가지로 나눈다.

1. N이 6으로 나눠 떨어지는 경우

2. N이 3으로 나눠 떨어지는 경우

3. N이 2로 나눠 떨어지는 경우

4. 그 외 (N이 3과 2 모두 나눠 떨어지지 않는 경우)

 

 

1. N이 6으로 나눠 떨어지는 경우

* N-1을 한 후 연산하는 횟수

* N / 2를 한 후 연산하는 횟수

* N / 3을 한 후 연산하는 횟수

 

위 3가지 방법 중 가장 적은 횟수를 가진 방법을 택한다.

 

 

2. N이 3으로 나눠 떨어지는 경우

* N-1을 한 후 연산하는 횟수

* N / 3을 한 후 연산하는 횟수

 

위 2가지 방법 중 가장 적은 횟수를 가진 방법을 택한다.

 

 

3. N이 2으로 나눠 떨어지는 경우

* N-1을 한 후 연산하는 횟수

* N / 2을 한 후 연산하는 횟수

 

위 2가지 방법 중 가장 적은 횟수를 가진 방법을 택한다.

 

 

4. 그 외 (N이 3과 2 모두 나눠 떨어지지 않는 경우)

* N-1을 한 후 연산하는 횟수

 

위 방법으로 연산한다.

 

public static int Count(int N){
        if (dp[N] == null){
            
            // 6으로 나눠지는 경우
            if (N % 6 == 0){
                dp[N] = Math.min(Count(N - 1), Math.min(Count(N / 2), Count(N / 3)) ) + 1;
            }
            // 3으로 나눠지는 경우
            else if (N % 3 == 0){
                dp[N] = Math.min(Count(N / 3), Count(N - 1)) + 1;
            }
            // 2로 나눠지는 경우
            else if (N % 2 == 0){
                dp[N] = Math.min(Count(N / 2), Count(N - 1)) + 1;
            }
            // 2와 3으로 나눠지지 않는 경우
            else{
                dp[N] = Count(N - 1) + 1;
            }
        }
        return dp[N];
} // Count

---

public static Integer[] dp;

/*
Integer 로 배열 선언시 null 값 취급이 가능. (초기값 null)
int 로 배열 선언시 null 값 취급 불가능. (초기값 0)
*/

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

public class Main{

    public static Integer[] dp;
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        
        // 1 ~ N 연산 횟수 저장
        dp = new Integer[N + 1];
        dp[0] = dp[1] = 0;
        
        bw.write(Count(N) + "\n");

        bw.flush();
        bw.close();
    }

    public static int Count(int N){
        if (dp[N] == null){
            
            // 6으로 나눠지는 경우
            if (N % 6 == 0){
                dp[N] = Math.min(Count(N - 1), Math.min(Count(N / 2), Count(N / 3)) ) + 1;
            }
            // 3으로 나눠지는 경우
            else if (N % 3 == 0){
                dp[N] = Math.min(Count(N / 3), Count(N - 1)) + 1;
            }
            // 2로 나눠지는 경우
            else if (N % 2 == 0){
                dp[N] = Math.min(Count(N / 2), Count(N - 1)) + 1;
            }
            // 2와 3으로 나눠지지 않는 경우
            else{
                dp[N] = Count(N - 1) + 1;
            }
        }
        return dp[N];
    } // Count

}

---

[ 2회차 풀이 / (1/28) ]

[접근 방법]

풀이 과정은 1회차와 같다.

 

실행 시간에 대한 고민을 하게 되었다.

주어진 실행 시간은 0.15초 이다.

1초에 2000만번의 연산이 되기 때문에, 0.15초는 약 300만번의 연산이 이루어질 수 있다.

N의 범위가 1부터 100만이므로, 

O(NlogN)  = 100만 * 6 = 600만

O(N) = 100만

 

O(N)의 시간복잡도를 가진 알고리즘을 채택해야 한다.

 

아래 JAVA 코드는 O(N)의 시간복잡도를 가진다.

 

[JAVA 코드]

// 1463 - 1로 만들기
import java.util.*;
import java.io.*;

class Main {
    
    public static void main(String[] args) throws IOException {
       
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        // N값이 1이 되는데 사용된 최소연산 횟수
        Integer[] DP = new Integer[N+1];
        DP[0] = DP[1] = 0;

        // 1. DP 연산
        for(int i=1; i<=N; i++){

            if (DP[i] == null){
                // 1-1. i가 6으로 나눠 떨어지는 경우
                if (i % 6 == 0){
                    DP[i] = Math.min(DP[i / 3], Math.min(DP[i / 2], DP[i - 1])) + 1;
                }
                // 1-2. i가 3으로 나눠 떨어지는 경우
                else if (i % 3 == 0){
                    DP[i] = Math.min(DP[i / 3], DP[i - 1]) + 1;
                }
                // 1-3. i가 2로 나눠 떨어지는 경우
                else if (i % 2 == 0){
                    DP[i] = Math.min(DP[i / 2], DP[i - 1]) + 1;
                }
                // 1-4. 2와 3 모두 나눠 떨어지지 않는 경우
                else {
                    DP[i] = DP[i - 1] + 1;
                }
            }
        }

        // 2. 출력
        bw.write(DP[N] + "\n");
        bw.flush();
        
        bw.close();
        br.close();
    }
}


/*
 * 실행 시간 0.15초 = 약 300만번 연산
 * 
 * N의 범위 (1 <= N <= 100만)
 * O(NlogN) = 100만 * 6 = 600만
 * O(N) = 100만
*/

 

[Rewind]

1. 어려웠던 점

- 1회자 풀었던 접근 방식이 생각나지 않았다.

- DP의 적절한 자료형을 생각해내지 못했다. (Integer[], int[])

 

2. 개선 방향

- Integer 배열을 사용하는 상황을 잘 인식해야 한다.