[c++/백준] 1463 1로 만들기

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

1463번: 1로 만들기

x가 2, 3, 4일 때는 직접 계산하기 쉽다. 

그 이후 생각할 것이 많은데 재귀를 이용해서 풀게되면 시간 초과가 생길 수 있다. 

 

다이나믹 프로그래밍을 사용해서 풀면 되는데 어렵게 생각하지 않고 재귀를 배열로 나타낸다고 생각하면 될 것 같다. 

 

x가 5부터 어떻게 되는지는 아래 코드에 자세하게 써놨다. 

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	
	vector<int> dp(1000001, 0);

	dp[2] = 1;
	dp[3] = 1;
	dp[4] = 2;

	for (int i = 5; i <= n; i++) {
		//i에서 1을 빼고 i-1의 연산횟수 더함
		if (i % 2 != 0 && i % 3 != 0) {
			dp[i] = dp[i - 1] + 1;
		}
		//2로 나누어 떨어지는 연산 과정과 3으로 나누어 떨어지는 연산 과정 중
		// min값을 넣어줘야함
		else if (i % 2 == 0 && i % 3 == 0) {
			dp[i] = min(dp[i / 2] + 1, dp[i / 3] + 1);
		}
		//min(2로 나누어 떨어지는 연산 과정, i-1을 했을 때 연산과정)
		else if (i % 2 == 0) {
			dp[i] = min(dp[i / 2] + 1, dp[i - 1] + 1);
		}
		//min(3으로 나누어 떨어지는 연산 과정, i-1을 했을 때 연산과정)
		else if (i % 3 == 0) {
			dp[i] = min(dp[i / 3] + 1, dp[i - 1] + 1);
		}
	}
	cout << dp[n];
	return 0;
}

사실 코린이라 피보나치수열 dp 말고는 dp 처음 풀어보는데 규칙 찾는게 어렵지 dp 자체는 그리 어렵지 않았을지도..? 그치만 규칙 찾고 뭐 하는게 너무 까다로움 ㅜㅜ