BaekJoon(1463)::1로 만들기

문제

1463번: 1로 만들기

문제파악

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

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

최소 연산횟수를 구하는 문제. 즉, DP를 사용하면 해결이 가능해 보인다.

문제풀이

해당 문제도 dp를 이용하면 풀수 있을 것이며, 그중 나의 경우 반복문을 이용해서 풀 생각이다.

dp[n] = dp[n-1] + 1는 기본적으로 가능한 횟수이다.

 

그리고 각 나누어떨어지는 상황 즉, 2로 나누는 연산과 3으로 나누는 연산과의 횟수를 비교해서 작은 값을 저장해 주면 된다.

#include<iostream>
using namespace std;

int min(int a, int b) {
	return a > b ? b : a;
}


int main() {

	int dp[1000001] = { 0, };

	dp[1] = 0;

	int n;
	cin >> n;

	for (int 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);
		}
	}

	cout << dp[n] << endl;

	return 0;
}