[C++] BOJ 1463 / DP (1로 만들기, 점화식 첫 도전)

문제 분석

 

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

BFS로도 구현이 가능하지만, DP로 훨씬 깔끔하게 구현이 가능하다.

어떠한 문제에 DP를 적용해야 하는지 깨닫기 위해서는 많은 문제를 풀면서 습득해야 한다.

 

해결 방법

DP 문제는 공통적인 해결 방법을 갖는다.

1. 테이블 정의하기

2. 점화식 찾기

3. 초기값 정의하기

이다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
int arr[1000001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i=2;i<=n;i++) {
        arr[i] = arr[i-1] + 1;
        if(i%3 == 0) {
            arr[i] = min(arr[i], arr[i/3] + 1);
        }
        if(i%2 == 0) {
            arr[i] = min(arr[i], arr[i/2] + 1);
        }
    }
    cout << arr[n];
}

 

후기

점화식만 똑바로 세운다면 구현이 어렵지는 않을 것이다.

DP문제는 앞에서 사용한 정보를 다시 사용하는 것이므로, "재사용"에 집중하여 분석하면 찾기 쉬울 것이다.

해당 문제가 본인의 첫 DP문제였다. 여태 다른 문제를 풀 때는 크게 느끼지 못했던 재미를 처음 느꼈다. 앞으로 DP와 친해질 것 같은 예감이 든다.