[BOJ] 1463. 1로 만들기(DP 기초)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

    - 정수 X에 사용할 수 있는 연산

      ㄴ if(X%3==0) X /= 3;

      ㄴ if(X%2==0) X /= 2;

      ㄴ X -= 1;

    - 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용하여 1을 만들 수 있는 최소 횟수

  3. Create solution plan (select Algorithm, Data structure)

    - DP(Dynamic Programming)

  4. Prove the plan (check performance time and usage memory)

    - 1 < N < 10^6

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

     DP를 이용하여 풀기 위해서는 "점화식"이 가장 중요하다. 규칙을 찾아보자.

     X = 1-> 0

     X = 2 -> 1

     X = 3 -> 1

     X = 4 -> 2

     X = 5 -> 3

     X = 6 -> 2

     X = 7 -> 3

     X = 8 -> 3

     X = 9 -> 2

     X = 10 -> 3

    모든 숫자는 '-1' 연산을 수행할 수 있으므로 i-1의 최소 연산 횟수 DP[i-1]을 참조하게 되고,

    2로 나누어 떨어질 경우, i/2의 최소 연산 횟수 DP[i/2]를 참조하게 되고,

    3으로 나누어 떨어질 경우, i/3의 최소 연산 횟수 DP[i/3]을 참조하게 된다.

    여기서,

    1. DP[i-1]가 1이 되기 위한 최소 연산 횟수 + 1

    2. DP[i/2]가 1이 되기 위한 최소 연산 횟수 + 1

    3. DP[i/3]가 1이 되기 위한 최소 연산 횟수 + 1

    의 최솟값이 i의 최소 연산 횟수가 된다.

    DP[3] = min(DP[1] + 1, DP[2] + 1)

    DP[4] = min(DP[2] + 1, DP[3] + 1)

    DP[5] = min(DP[4] + 1)

    DP[6] = min(DP[5] + 1, DP[3] + 1, DP[2] + 1)

    DP[7] = min(DP[6] + 1)

    DP[8] = min(DP[7] + 1, DP[4] + 1)

#. Code

#include <cstdio>
#include <algorithm>
using namespace std;
 
int dp[1000001];
 
int main(void)
{
    int n, i;
    scanf("%d", &n);
 
    for (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);
    }
 
    printf("%d\n", dp[n]);
 
    return 0;
}

line 12) 2는 2로 나누어도 1이고, 1을 빼도 1이 되므로 1만 참조하면 된다. 그래서 2부터 반복문을 돌려도 무관!

line 13) 우선 '-1' 연산을 수행하였을 때, dp[i-1]의 연산 횟수 + 1을 저장

line 14) i가 2로 나누어 떨어질 때, dp[i/2]의 최소 연산 횟수 + 1과 line 13에서 저장한 dp[i]와의 최솟값 저장

line 15) i가 3으로 나누어 떨어질 때, dp[i/3]의 최소 연산 횟수 + 1과 line 13에서 저장한 dp[i]와의 최솟값 저장