[BOJ/C++] 1463 1로 만들기 : DP

문제

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

풀이

DP 문제를 처음 풀어봐서 어떤 방식으로 푸는지 찾아봤다.

DP : 문제를 더 작은 단위로 쪼개서 해결하는 알고리즘

• 사용하기 위한 조건

  • 부분 문제들이 반복
    ex) 피보나치 수
    n번째 항 = n-1번째 항 + n-2번째 항
    
    
  • 최적 부분 구조 (문제의 정답을 작은 문제의 정답으로부터 구할 수 있는지)
    ex) 최단경로 구하기
    A->C 최단경로(큰 문제) = A->B 최단경로(작은문제) + B->C 최단경로(작은문제)

• DP 알고리즘을 적용할 수 있게 점화식을 도출하는 것이 핵심
  
  

sol)

코드

#include <iostream>
#include <algorithm>

using namespace std;

int dp[1000000];

int main() {
	int N;

	cin >> N;
	dp[0] = 0;
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;

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

	cout << dp[N];

	return 0;
}