[백준 BOJ][DP] 1463 1로 만들기

1463_1로 만들기

 

링크

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

 

풀이

 

 

우선 DP[N]을 정수 N을 1로 만드는 데 필요한 최소 연산 횟수라고 정의합시다.

N은 N-1에서 1을 더해 만들 수 있고, N/2에서 2를 곱해 만들 수 있고, N/3에서 3을 곱해 만들 수 있습니다.

 

DP[N]은 DP[N-1]과 DP[N/2]와 DP[N/3]에서 한 번의 연산을 더 수행해서 만들 수 있습니다.

하지만 DP[N]은 최소 연산 횟수이기 때문에,

DP[N] = min(DP[N-1]+1, DP[N/2]+1, DP[N/3]+1)

라는 식이 생깁니다.

 

이걸 조건마다 코드로 구현하면 됩니다.

 

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

//1463_1로 만들기 #include <iostream> #include <algorithm> using namespace std;   int DP[1000001];   int main() {     int n;     int i;       cin >> n;       for (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);        //min(DP[i-1]+1, DP[i/2]+1, DP[i/3]+1)     }       cout << DP[n] << endl;       return 0; } Colored by Color Scripter

cs