[BOJ]1463-1로 만들기

1463

뭔가 dp일 것 같았는데 코드를 어떻게 작성해야 할지 모르겠어서 풀이를 찾아봤다.

N부터 시작하는 걸 생각했는데 N까지 도달하는 풀이였다.
생각보다 엄청 짧은 풀이여서 놀랐다.
규칙찾기 너무 어렵드아.

성공코드

#include <iostream>
using namespace std;

int arr[1000002];

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

	cin >> N;

	for (int i = 2; i <= N; i++)
	{
		arr[i] = arr[i - 1] + 1;

		if (i % 3 == 0)
		{
			arr[i] = min(arr[i], arr[i / 3] + 1);
		}
		
		if (i % 2 == 0)
		{
			arr[i] = min(arr[i], arr[i / 2] + 1);
		}
	}

	cout << arr[N];
}

참고자료

---

c++ 1463 문제풀이