[C++] 백준 1463. 1로 만들기

🌽 문제

🥕 입출력

🥔 풀이

dp 문제라는 걸 알고 있었어서 규칙부터 찾기 시작해서 풀었다.
근데 나중에 문제 풀 때 dp인걸 모르면 어쩌지

🥬 코드

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

int n, dp[1000000] = { 0, };

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	dp[2] = 1;
	dp[3] = 1;

	cin >> n;
	for (int i = 4; i <= n; i++) {
		if (i % 6 == 0) {
			dp[i] = min(min(dp[i / 2], dp[i / 3]), dp[i - 1]) + 1;
		}
		else if (i % 2 == 0) {
			dp[i] = min(dp[i / 2], dp[i - 1]) + 1;
		}
		else if (i % 3 == 0) {
			dp[i] = min(dp[i / 3], dp[i - 1]) + 1;
		}
		else {
			dp[i] = dp[i - 1] + 1;
		}
	}
	cout << dp[n];
	return 0;
}

🥜 채점

긴 연휴 때문 아니고 그냥 하기 싫어서 애써 외면하던 알고리즘을 이제야 열었다.
꾸준히는 정말 어려워