[백준][1463번] 1로 만들기

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

1463번: 1로 만들기

 

풀이과정

1. dp를 이용했다.

 

2. -1, n/3, n/2  3가지 방식을 이용하면 

 

dp[N] = min( n-1, n/3, n/2) + 1로 점화식을 구할 수 있다.

 

*마지막이 n - 1 인경우 + 1을 하면 dp[N]이 된다. 이와 같이 3가지 방식 중 가장 최솟값을 뽑아 내면 된다.

 

소스코드

#include <stdio.h>
#include <algorithm>
using namespace std;
int dp[1000001];

int solution(int n)
{
	if (n <= 1) return 0;
	if (dp[n] > 0) return dp[n];

	dp[n] = solution(n - 1) + 1;
	if (n % 3 == 0) {
		int tmp = solution(n / 3) + 1;
		dp[n] = min(dp[n], tmp);
	}
	if (n % 2 == 0) {
		int tmp = solution(n / 2) + 1;
		dp[n] = min(dp[n], tmp);
	}
	return dp[n];
}

int main()
{
	int n;
	scanf("%d", &n);
	dp[1] = 0;
	dp[2] = 1;
	printf("%d\n", solution(n));
}