백준 1363 1로 만들기 [C++]

작성일 | In |

Problem : 1로 만들기

유형 : DP

문제 해석

  • 주어진 수를 1로 만드는 최소 연산 수를 구하여라

해결 전략

  • 이전에 계산된 결과가 , 이후의 결과에 영향을 준다.
    • 4를 구할때 들어간 연산이, 8를 구할때 들어간 연산에 영향을 준다. /2
  • 점화식을 세운다.
    • dp[n] 은 n이 1로 되는 최소 연산수
    • dp[n] 이 시도할 수 있는것은 n-1, n/2, n/3 이중 가장 작은 값을 구한다.

구현

  • 언제나 가능하고, 가장 비효율적인 -1 연산부터 처리한다.
  • 이후 나누어짐이 가능함 여부를 보고 /2 , /3 연산을 하며 갱신해나간다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e6 + 2;
int dp[MAX];
int n;

void solve() {
    cin >> n;
    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] << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    solve();

    return 0;
}

피드백

  • 벌써 6번째 풀어보는 문제이다. DP문제를 많이 안풀어본것 같아서 다시 차근차근 풀어보려고한다.