1463번-1로 만들기

문제

---

/2, /3, -1을 써서 최소한의 횟수로 입력되는 숫자를 1로 만드는 것이 문제

문제 해결을 위한 준비

---

DP - 이전 값과 비교해서 최적의 값을 만들기 위함.

코드

---

#include <iostream>

using namespace std;

int DP[1000010] = {0};

int Min(int a, int b){ return a < b ? a : b;  }

int Solution(int n)
{
    for(int num = 2; num <= n; num++)
    {
        DP[num] = DP[num - 1] + 1;
        if(num % 3 == 0) DP[num] = Min(DP[num], DP[num / 3] + 1);
        if(num % 2 == 0) DP[num] = Min(DP[num], DP[num / 2] + 1);
    }

    return DP[n];
}

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

    cout << Solution(n);  
    
    return 0;
}

풀이

---

최적의 값을 구해야 하기 때문에 dp로 풀어야 한다. dp는 이런 식으로 만들었다

dp[a] = b : a를 1로 만드는 최소한의 횟수는 b이다. 

점화식은 위에 나와있는 3가지의 방법을 식으로 만들면 된다

1. 3으로 나눌 수 있다면 3으로 나눈다 : dp[i / 3]
2. 2으로 나눌 수 있다면 2으로 나눈다 : dp[i / 2]
3. -1 뺀다 : dp[i - 1] 

원리

1부터 i까지 최적의 횟수를 구하면서 i를 3가지 방법으로 계산해서 각각의 값에 들어있는 최적의 휫수 중에 가장 작은 값을 넣으면 끝

 

처음 dp문제를 풀었을 땐 하루종일 고민하고 정답코드를 봐도 이해하지 못했던걸

두 번째 문제에 오면서 6시간으로 단축되었다. wow