(c++)백준 1463번: 1로 만들기

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

1463번: 1로 만들기

점화식 

dp[i]:정수 i를 1로 만들기 위해 연산을 사용하는 최소 횟수

 

dp[x] = min(1+dp[x-1], 1+dp[x/2])  if(x%2==0)

dp[x] = min(1+dp[x-1], 1+dp[x/3])  if(x%3==0)

dp[x] = 1+dp[x-1]  if(x%2!=0 && x%3!=0)

 

#include <iostream>
#include <algorithm>//min
using namespace std;

int N;
int dp[1000001];//최소 연산 사용 횟수 저장

void DP() {
	//초기값 설정
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
	for (int i = 4; i <= N; i++) {
		//3으로 나누어 떨어질 때
		if (i % 3 == 0) {
			dp[i] = min(1 + dp[i - 1], 1 + dp[i / 3]);
		}
		//2로 나누어 떨어질 때
		else if (i % 2 == 0) {
			dp[i] = min(1 + dp[i - 1], 1 + dp[i / 2]);
		}
		//2,3으로 나누어 떨어지지 않을 때
		else {
			dp[i] = 1 + dp[i - 1];
		}
	}
	cout << dp[N] << endl;
}

int main() {
	cin >> N;
	DP();
	return 0;
}