[C언어] 백준 1463 : 1로 만들기

생각의 흐름

3으로 나누어 떨어지는 경우, 2로 나누어 떨어지는 경우를 생각했다. 중요한건 큰 덩어리를 작은 덩어리로 만들고, 그 덩어리를 기억하면서 큰 덩어리를 없애야한다.
1은 0, 2는 1, 3은 1이다. 이건 고정이고, 3, 6, 9, 12, 15... 3의 배수인 경우를 예를 들어보자.
3 = 1, 6 = 6 / 3 + 1 -> 2, 9 = 9 / 3 + 1 -> 2, 12 = 12 / 3 + 1 -> 3...
따라서 점화식은 dp[i] = dp[i / 3] + 1이고, 2일경우도 같다. 하지만 우리는 -1일 경우도 고려해주어야 하는데, 이를 위해 dp[i] = dp[i - 1] + 1을 설정해주어 최솟값을 골라주는 작업을 진행했다.
2와 3으로 나누어떨어지지 않으면 직전값 + 1이 dp[i]가 된다.
다시말하면 dp[i]는 2와 3으로 나누어 떨어지지 않기에 -1을 진행해야한다.

#include <stdio.h>
#define min(a, b) (a < b ? a : b)

int main()
{
	int dp[1000001];
	int i, n;
	scanf("%d", &n);
	dp[2] = 1;
	dp[3] = 1;
	i = 4;
	while (i <= n)
	{
		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);
		}
		i++;
	}
	printf("%d", dp[n]);
}

https://canoe726.tistory.com/39
앞부분 논리설명이 좋았다.