BOJ 1463번 : 1로 만들기

문제를 읽어보면 알겠지만, 무조건 큰 수를 작게 만드는 것의 반복이 아니다. 예를 들면

10을 (/2, -1, /2, /2)를 하면, 각 순서마다 가장 작은 값을 뽑아왔지만, (-1, /3, /3) 처럼, 나누는게 우선순위가 아니였다. 즉, /3,/2,-1 순서가 우선순위를 가지지 않는다.

 

그래서 1부터 4까지의 수를 하나씩 해보았다.

 

n = 1, 0번

n = 2, 1번

n = 3, 1번

n = 4,

   1) -1 을 할 경우, n = 3 이 되므로 2번.

   2) /2 를 할 경우, n = 2 가 되므로 2번.

   3) /3 은 불가능.

 

즉, dp[n] 은

(n-1)를 1로 만드는 최소횟수 +1 또는

(n/2)를 1로 만드는 최소횟수 +1 또는

(n/3)을 1로 만드는 최소횟수 +1 이 될 것이다.

 

이런식으로 dp 배열에 인자를 구성하려면, 들어갈 인자는 일단 '값'이 아닌 '횟수'가 될 것이다.

이 것을 점화식으로 바꾼다면, 아래 식으로 구성할 수 있다.

 

dp[i] = (dp[i - 1] + 1); dp[i] = (MIN(dp[i], dp[i / 2] + 1); dp[i] = (MIN(dp[i], dp[i / 3] + 1);

 

<소스코드>

#include<iostream>
#include<stdlib.h>
#include<vector>
#define MIN(X,Y) ((X)<(Y)? (X):(Y))
using namespace std;
int main() {
    vector<int> dp(2,0);
    int n = 0;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        dp.push_back(dp[i - 1] + 1);
        if( !(i % 2)) dp[i] = (MIN(dp[i], dp[i / 2] + 1));
        if (!(i % 3)) dp[i] = (MIN(dp[i], dp[i / 3] + 1));
    }
    cout << dp[n];
}

 

문제 :

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

1463번: 1로 만들기