백준 1463 1로 만들기

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int memo[1000001];
int main() {
	int n;
	cin >> n;
	int count = 0;


	//cout << solve(n) << endl;
	for (int i = 2; i <= n; i++) {
		int case_1 = 10000000;
		if (i % 2 == 0) { case_1 = memo[i / 2]; }

		int case_2 = 10000000;
		if (i % 3 == 0) { case_2 = memo[i / 3]; }

		int case_3 = memo[i - 1];

		memo[i] = min(case_1, min(case_2, case_3))+1;
	}

	cout << memo[n] << endl;
}

티스토리는 코드 뷰어를 만들어 줬으면 좋겠다.

어쨋든.. 생각보다 짧게 나와서 신기했던 코드

첨엔 재귀로 풀었으나... 멍청한 나는 스택 오버플로우가 뜨는걸 보았다.

그래서 반복문으로 바꿨는데

햐 진짜 재귀를 반복문으로 바꾸는거 왜이렇게 어려운지 모르겠다.

솔직히 문제 푸는것보다 어려웠다.

memo[n]은 'n이란 숫자를 1로 만들려면 몇번 연산 해야 하는가' 를 뜻한다.

점화식은 DP(n)  = min( DP(n/3) + DP(n/2) + DP(n-1) ) + 1