[BAE/<JOON> 문제풀이] 1463. 1로 만들기 (DP.001)

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

1463번: 1로 만들기

난 DP를 잘 못한다.

 

알고리즘 톡방의 어떤 분의 블로그에서 본 내용인데 DP를 못할 때 특효약은 DP 200문제를 풀어보는거라고 한다.

 

맞는말 같다. 다른 알고리즘들은 난이도가 어려워져도 해당 알고리즘의 틀에서 크게 벗어나지 않는 반면에 

 

DP는 문제 자체가 다양하고 다른 알고리즘들과도 비교적 쉽게 연결이 가능해서 더 어려운것 같다.

 

오늘부터 DP문제만 풀어봐야겠다. 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> arr;
    arr.assign(n + 1, 0);
    for (int i = 2; i <= n; i++) {
        int c1 = arr[i - 1] + 1;  
        if (i % 2 == 0) {
            if (arr[i / 2] + 1 < c1) c1 = arr[i / 2] + 1;
        }
        if (i % 3 == 0) {
            if (arr[i / 3] + 1 < c1) c1 = arr[i / 3] + 1;
        }
        arr[i] = c1;
    }
    cout << arr[n];
    return 0;
}