[백준 - 1463] 1로 만들기

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

int DP[1'000'001];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;

	for (int i = 2; i <= N; ++i)
	{
		//최악의 방법으로 일단 구해놓는다.
		DP[i] = DP[i - 1] + 1;
		if (i % 3 == 0) DP[i] = min(DP[i], DP[i / 3] + 1);
		if (i % 2 == 0) DP[i] = min(DP[i], DP[i / 2] + 1);
	}
	cout << DP[N];
	return 0;
}

---

||사고 과정

지금 DP를 공부중이라 다른 사람의 코드를 보고 작성한 코드이다.

처음에 혼자 풀때는 규칙을 찾아보면서 이게 왜 DP인지는 알았으나 식을 도출하기가 어려웠다ㅠ

 

시간제한이 0.15초라 N번만큼 loop를 도는게 아닌거 같았지만 잘 되더라..

암튼 여기서 중요했던건 역시 DP인만큼 이전 값을 활용한다는것!

---

||사용 기법

• DP