[백준] 1463 1로 만들기 문제풀이 C++ :: DP(다이나믹 프로그래밍) :: DANIDANI

1463 1로 만들기

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

DP(Dinamic Programming, 다이나믹 프로그래밍) 으로 푸는 문제!

시간 복잡도는 O(N)

---

bottom-up 방식으로 for문을 사용해서 풀었다.

index 가 n+1 인 배열을 만든다.

index가 문제에서의 연산하는 숫자!

dp [1] = 0로 초기화를 해준다. (1일 경우 연산 안 해도 됨)

 

할 수 있는 연산은 3가지

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.

3가지 경우의 최솟값을 저장하면 된다.

 

예를들어 dp [4]인 경우 2로 나누어 떨어지는데

dp[4/2] + 1 = dp [2] + 1 = 2,

dp [3] + 1 = 2.

둘 중 최솟값, 2가 저장된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int n;
	cin >> n ;
	vector<int> dp(n + 1);

	//bottom-up
	dp[1] = 0;
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + 1;
		if (!(i % 3)) dp[i] = min(dp[i],dp[i / 3] + 1);
		if (!(i % 2)) dp[i] = min(dp[i], dp[i / 2] + 1);
	}

	cout << dp[n] << endl;
	return 0;
}