챕터3-2. DP | 문제 풀이1 - (1) 백준 No.1463 : 1로 만들기

1로 만들기 문제

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

문제요약

어떤 정수 N에 대해 다음과 같은 연산중 하나를 선택할 수 있다.
1) 3으로 나누어 떨어지면 3으로 나눈다.
2) 2로 나누어 떨어지면 2로 나눈다.
3) 1을 뺀다.
이를 반복하여 1을 만들려고 하는데 연산을 사용하는 횟수의 최소값을 출력해라.

해결방법 - 다른 문제에도 공통적으로 적용됨

1. D[N]에 어떤 값을저장할 것인지 문장으로 정의해줘야 한다.
- 대부분의 다이나믹 문제는 문제에서 구하라는 값을 그대로 D[N]에 넣어주면 된다.
- 따라서, D[N]= "정수 N을 1로 만드는데 필요한 연산 횟수의 최소값" 이라고 정의해 줄 수 있다.

2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다.
- N이 주어지면 1이 될 때 까지 매번 아래의 3가지 연산방법 중 한가지를 선택할 수 있는데,
   N에 대해 각 연산을 한번만 수행한 경우는 아래와 같다.

Case1) -1을 해주는 경우
N -> N-1 -> ... -> 1 이 되는데, 한번 N-1을 해준경우 다음과 같이 표현할 수 있음.
D[N] = D[N-1] + 1
D[N-1] + 1 는 (N-1을 1로 만드데 필요한 최소 연산횟수) + (N을 N-1으로 만드는 연산횟수) 을 의미함

Case2) 2로 나눠주는 경우
N -> N/2 -> ... -> 1 이 되는데, 한번 N/2를 해준경우 다음과 같이 표현할 수 있음.
D[N] = D[N/2] + 1
D[N/2] + 1 는 (N/2을 1로 만드데 필요한 최소 연산횟수) + (N을 N/2으로 만드는 연산횟수)을 의미함

Case3) 3으로 나눠주는 경우
N -> N/3 -> ... -> 1 이 되는데, 한번 N/3을 해준경우 다음과 같이 표현할 수 있음.
D[N] = D[N/3] + 1
D[N/3] + 1 는 (N/3을 1로 만드데 필요한 최소 연산횟수) + (N을 N/3으로 만드는 연산횟수)을 의미함

결론적으로, 각 단계에서 3가지 연산 모두에 대해 1을 만드는데 필요한 연산횟수를 각각 구한 뒤,
최소값을 택하여 D[N]에 저장하면 되므로, D[N] = min( D(N-1) + 1, D(N/2) + 1, D(N/3) + 1 )의 점화식을 생각할 수 있다.
단, D(N/2) + 1 과 D(N/3) + 1 은 2와 3으로 나누어 떨어져야 구할 수 있는 것이므로
한번에 3개를 모두 구해서 min함수를 사용할 수 없고, 아래에서 구현방 방식대로 두 개씩 비교해가며 최소값을 구하면 된다.

3. 다이나믹 프로그래밍 방법을 적용할 수 있는 문제인지 확인 => 1, 2번을 거쳐야 이게 잘 보임.
- 아래와 같이 큰 문제를 작은 문제로 쪼갤 수 있으며, 작은 문제도 큰 문제와 같은 방법으로 풀 수 있고, 작은 문제들이 겹친다.
   (Overlapping SubProblem)
- 문제의 정답을 작은 문제의 정답으로부터 구할 수 있으며, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
   (Optimal Substructure)

4. 코드구현
* Top-Down, Bottom-Up 방식 모두 최종값이 결정되는 순서는 d[1], d[2], d[3],,, 순이다. (구현방식의 차이일 뿐)

<Top-Down 방식>

(1) 구현
-> '재귀호출' 방식으로 구현
- 동작 방식을 이해하기 쉽도록 아래의 Bottom-Up 방식을 참고하자.
- -1을 해주는 연산은 어느 수에도 항상 적용이 가능하므로 맨 첫번째에 시행을 하여 비교의 기준이 된다.

int d[1000000] = {0};   // 1에서 1로 가는건 연산을 필요로 하지 않으므로 d[1] = 0, 그냥 모두 d[0~99] = 0

// N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수
int getSmallestCalCount(int n)
{
    if (n <= 1)
        return d[n];
    
    else if (d[n] > 0)  // n >= 2 경우, d[n] > 0 이면 이미 계산된 결과가 있음을 의미하므로 바로 결과반환
        return d[n];
    
    else
    {
        // 모든 수에서 가능한 연산인 -1을 먼저 해준다.
        d[n] = getSmallestCalCount(n-1) + 1;

        // 2으로 나눌 수 있어서 2으로 나눈 경우, 위에서 계산한 연산횟수보다 작은 연산횟수를 가지는지 확인
        if( n%2 == 0)
        {
            int temp;
            temp = getSmallestCalCount(n/2) + 1;
            if (d[n] > temp)
                d[n] = temp;
        }
            
        // 3으로 나눌 수 있어서 3으로 나눈 경우, 위에서 계산한 연산횟수보다 작은 연산횟수를 가지는지 확인
        if( n%3 == 0)
        {
            int temp;
            temp = getSmallestCalCount(n/3) + 1;
            if (d[n] > temp) 
                d[n] = temp;
        }
            
        // 이 위치에 도달하는 순간 d 1개의 값이 정해짐.
        return d[n];   
    }
}

(2) 시간복잡도
= 배열에 채워 넣어야하는 값의 수 x 1칸을 채우는 복잡도
- 배열에 채워 넣어야하는 값의 수 : N
- 1칸을 채우는 복잡도 : getSmallestCalCount(n-1) + 1 에서 한 번의 연산, 
                                   getSmallestCalCount(n/2) + 1 에서 한 번의 연산, 
                                   getSmallestCalCount(n/3) + 1 에서 한 번의 연산.
                                   이렇게해서 총 3번인데 이걸 시간복잡도로 나타내면 O(1)
- 따라서 전체 시간복잡도는 N * O(1) = O(N)

<Bottom-up 방식>

(1) 구현
-> 'for문을 이용한 반복문'으로 구현
- -1 연산은 어느 수에도 항상 적용이 가능하므로 맨 첫번째에 시행을 하여 비교의 기준이 된다.
- for문 안에 있는 것들을 Top-Down 방식에서 n인자를 i인자로 수정해주고, 함수호출을 d로 변경해주면 됨.

int d[1000000] = {0};   // 1에서 1로 가는건 연산을 필요로 하지 않으므로 d[1] = 0, 그냥 모두 d[0~99] = 0

// N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수
int getSmallestCalCount(int n)
{
    if (n <= 1)
        return d[n];
    
    else if (d[n] > 0)  // n >= 2 경우, d[n] > 0 이면 이미 계산된 결과가 있음을 의미하므로 바로 결과반환
        return d[n];
    
    else
    {
        for (int i = 2; i <= n; i++)
        {
            // 모든 수에서 가능한 연산인 -1을 먼저 해준다.
            d[i] = d[i-1] + 1;

            // 2으로 나눌 수 있어서 2으로 나눈 경우, 위에서 계산한 연산횟수보다 작은 연산횟수를 가지는지 확인
            if (i%2 == 0)
            {
                int temp;
                temp = d[i/2] + 1;
                if (d[i] > temp)
                    d[i] = temp;
            }
            
            // 3으로 나눌 수 있어서 3으로 나눈 경우, 위에서 계산한 연산횟수보다 작은 연산횟수를 가지는지 확인
            if (i%3 == 0)
            {
                int temp;
                temp = d[i/3] + 1;
                if (d[i] > temp)
                    d[i] = temp;
            }

            // 이 위치에 도달하는 순간 d 1개의 값이 정해짐.
        }
        return d[n];
    }
}

 
(2) 시간복잡도
= for 문의 반복 횟수 = O(N)