[c++] 백준 알고리즘 공부 1463번

처음 냈던 오답

#include <iostream>
#include <math.h>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);
	int n;
	cin >> n;
	int cnt = 0;
	int k[20];
	for (int i = 1; i < 20; i++)
	{
		k[i] = pow(2, i);
	}
	int q = 1;
	while (true)
	{	
		while (true)
		{
			if (n % 2 == 0 &&n==k[q]) {
				cnt++;
				n /= 2;
				q = 1;
			}
			if (n < k[q])
				break;
			q++;
		}
		if (n == 1)
			break;
		if (n % 3 == 0) {
			cnt++;
			n /= 3;
			continue;
		}
		else {
			n -= 1;
			cnt++;
		}
		
	}
	cout << cnt;
}

너무 안일하게 생각을 하여 오답이 나왔다,,

#include <iostream>

using namespace std;

int N;
int D[1000001];

int main() {
	cin >> N;
	D[1] = 0;
	D[2] = 1;
	D[3] = 1;

	for (int i = 4; i <= N; i++) {
		D[i] = D[i - 1] + 1;
		if (i % 3 == 0) D[i] = min(D[i / 3] + 1, D[i]);
		if (i % 2 == 0) D[i] = min(D[i / 2] + 1, D[i]);
	}

	cout << D[N];
}

간단하게 점화식으로 풀었으면 그나마 쉬웠는데 너무 단순하게 생각을 하게 된거 같다ㅜㅜ
DP 알고리즘을 좀 더 찾아보고 공부를 해야겠네,,