BOJ [1463] 1로 만들기

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

정수 X를 1로 만드는 연산의 최소 횟수를 구하는 문제이다.

① 3으로 나누기
② 2로 나누기
③ 1 빼기

1로 만드는 가장 빠른 것은 1번 연산이다. 그 다음은 2로 나누기, 1 빼기 순이 될 것이다.

숫자 1은 이미 1이므로 연산이 필요 없고 2와 3은 1번의 연산을 해야 한다.

int d[1000001] = { 0, 0, 1, 1, };

여기서 d[X]은 X을 나누는 최소 횟수이다.

배열의 인덱스는 X의 최대값인 10⁶ + 1 까지이며 0~3을 1로 만드는 최소 횟수를 초기화했다.

3까진 이미 정했으니 4부터 규칙을 차근히 생각해보면

숫자 4를 만드는 방법 : 2 * 2, 3 + 1
숫자 5를 만드는 방법 : 4 + 1
숫자 6를 만드는 방법 : 2 * 3, 3 * 2, 5 + 1
...

반복하다 보면

X * 3의 최소 횟수 = X의 최소 횟수 + 1
X * 2의 최소 횟수 = X의 최소 횟수 + 1
X + 1의 최소 횟수 = X의 최소 횟수 + 1

라는 결론에 도달한다.

#include <cstdio>

int d[1000001] = { 0, 0, 1, 1, };

int main() {

	int N;

	scanf("%d", &N);

	for (int i = 4; i <= N; i++)
	{
		int min = d[i - 1];

		if (i % 3 == 0)
		{
			if (min > d[i / 3])
				min = d[i / 3];
		}

		if (i % 2 == 0)
		{
			if (min > d[i / 2])
				min = d[i / 2];
		}

		d[i] = min + 1;
	}

	printf("%d\n", d[N]);
	return 0;
}