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

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

1463번: 1로 만들기

소스 코드 :

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

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int arr[1000001];
	int operation = 0;
	arr[1] = 0;
	arr[2] = 1;
	arr[3] = 1;
	int N;
	cin >> N;

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

	cout << arr[N];
}

마무리 : 처음에 풀 때는 문제에서 사용할 수 있는 연산 순으로 입력 수를 나누고 빼주었다. 그러면 예제에 나와있는 것들이 답이 나와 제출했지만 틀렸다고 하였다. 속으로는 역시 이렇게 쉽지는 않겠지라는 생각도 했다.

 계속 이 문제를 보았지만 어떻게 풀지 몰라 어떤 알고리즘을 사용하나 보았는데 다이나믹 프로그래밍을 사용해야한다고 되어있다. 그래서 손으로 문제를 풀어보니 다이나믹으로 풀어야 된다는 것을 깨닫고 그렇게 코드를 짰다.