백준 1463 (1로 만들기) c++

문제

1463번: 1로 만들기

n이 주어지면 n을 3으로 나누거나 2로 나누거나 1을 빼든가 해서 1로 되게하는 연산의 합이 최소를 구하는 것입니다.

1 ≤ n ≤ 1000000

예를 들어 n이 10이면 (10 -> 9 -> 3 -> 1) 총 3번의 연산이 최소가 됩니다.

 

bottom-up 방식으로 dp를 이용해 해결하였습니다.

1) n이 2로 나누어떨어지면 dp[n] = dp[n-1]과 dp[n/2] 중에서 작은 값에다가 1을 더해줍니다.

2) n이 3으로 나누어 떨어지면 dp[n] = dp[n-1]과 dp[n/3] 중에서 작은 값에다가 1을 더해줍니다.

3) n이 2와 3 모두 나누어 떨어지면 dp[n] = dp[n-1], dp[n/2], dp[n/3] 중에서 작은 값에다가 1을 더해줍니다.

4) 그 나머지 경우에는 그냥 dp[n-1] 에다가 1을 더해줍니다.

---

전체 코드 입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int dp[1000001];
int n;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    fill(dp, dp + 1000001, -1);
    cin >> n;
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 1;
    for (int i = 4; i <= n; i++) {
        if (i %2== 0 && i % 3 == 0)
            dp[i] = min(min(dp[i - 1], dp[i / 2]), dp[i / 3]) + 1;
        else if (i % 3 == 0)
            dp[i] = min(dp[i - 1], dp[i / 3]) + 1;
        else if (i % 2 == 0)
            dp[i] = min(dp[i - 1], dp[i / 2]) + 1;
        else dp[i] = dp[i - 1] + 1;
    }
    cout << dp[n];
    return 0;
}
 

 

※

bottom-up 방식에서 위에것이 뿌려지는 방식 입니다.