백준 1463: 1로 만들기 (C++)

문제 링크: www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

2~1000000까지 1로 만드는 최소 연산 횟수를 먼저 계산한다.

작은 수에 대해서 먼저 계산하고 그 값을 저장해 재활용함으로써 불필요한 연산을 줄일 수 있다.

 

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

#define MAX 1000001

int arr[MAX]; //1로 만드는 연산 횟수 저장

void count() {
	for (int i = 2; i <= MAX; ++i) {
		arr[i] = arr[i - 1] + 1;
		if (i % 2 == 0) arr[i] = min(arr[i], arr[i / 2] + 1);
		if (i % 3 == 0) arr[i] = min(arr[i], arr[i / 3] + 1);
	}
}

int main() {
	int in;
	count();
	scanf("%d", &in);
	printf("%d", arr[in]);
}