[알고리즘 문제] 백준1463 - 1로 만들기

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

1463번: 1로 만들기

비슷한 문제를 코딩테스트에서 본 적 있는데 당시에 못 풀었는데, dp로 접근하면 될 것 같습니다.

 

bottm-up 방식으로 풀었고, dp[n]에는 n을 1로 만드는 최소 횟수가 들어가 있습니다. 해결하는 방법은 전형적인 dp방법으로 이전에 계산했던 최소값을 현재 n을 구하는데 사용합니다. 

 

dp[n]에는 n숫자를 1로 만드는데 최소 횟수가 들어가 있다고 했습니다. 먼저 처음 dp[1]은 0로 초기화 해줍니다. 어떤 연산도 할 필요 없기 때문이죠. 그렇다면 이제 2부터 1~3번째 연산을 모두 해봅니다. 1~3연산을 하면서 최소횟수는 dp[n]에 넣는거죠.

 

예를 들어, n이 2인 경우 

 

1. 1을 뺀다

dp[1]이 0이고 1에서 +1을 하면(2에서 -1을하면와 같은 말) 2이기 때문에 1회 연산을 추가합니다. 그리고 현재 dp[n]에는 dp[n-1]에서 1회 연산 추가한 값을 가집니다. dp[n] = dp[n-1] +1

 

2. 2로 나누어 떨어지면, 2로 나눈다.

현재 dp[2]에는 1이 들어가 있습니다. 그런데 아직 n이 2와 3으로 나누어 떨어질 수 있기 때문에 이 부분을 또 검사해 줍니다. 만약 n이 2로 나누어 떨어진다면 dp[n/2]에 있는 값에 +1을 해줍니다. 왜냐하면 2로 나누어 떨어지기 때문에 2로 나누는 연산을 한번 했기 때문입니다.

 

이 경우는 n이 4인 경우, 4->2로 바로가는 경우 입니다. -1을 빼주는 4->3->2보다 1회 절약되기 때문에 2로 나누는 경우가 더 최소가 되겠죠. 현재 dp[n]에는 n을 1로만 뺀 경우만 존재하기 때문에 현재값과 dp[n/2]+1에서 최소값을 구해줍니다. 그리고 그 값을 dp[n]에 다시 넣어줍니다.

 

3. 3로 나누어 떨어지면, 3로 나눈다.

이 경우도 2번의 경우와 마찬가지 입니다.

 

위의 과정을 간단한 말로 설명해보면, 

n을 1로 만드는데 최소횟수를 dp[n]에 저장해보자 !!

3개의 연산횟수가 있으니, 아직 어떤걸로 해야 최소횟수인지 모르기 때문에 각 연산을 해보면서 dp[n]값을 계속 바꾸어 보자.

먼저 -1인 경우를 해보고 해당 최소횟수를 dp[n]에 저장하자. 근데 2로 나누었을 때 더 작은 최소값을 가질 수 있기 때문에 n/2한 최소횟수를 dp[n]에 저장하자. 마지막으로 3으로 나누었을 때 더 작은 최소값을 가질 수 있기 때문에 n/3한 최소횟수를 dp[n]에 저장해보자.

-> 한 사이클이 지나면 dp[n]에는 무조건 n을 1로 나누었을 때의 최소값이 저장되어 있다. 이 값을 다음 연산할 때 또 사용하자.

 

#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;
int dp[1000001];

int main()
{
    int n;
    cin >> n;

    dp[1] = 0;

    for (int i = 2; i <= n; i++)
    {
        dp[i] = dp[i - 1] + 1;

        if (i % 2 == 0)
        {
            dp[i] = min(dp[i], dp[i / 2] + 1);
        }
        if (i % 3 == 0)
        {
            dp[i] = min(dp[i], dp[i / 3] + 1);
        }
    }

    cout << dp[n];
    return 0;
}