[C/C++] 백준 1463, Dynamic programming

1463번: 1로 만들기 (acmicpc.net)

1463번: 1로 만들기

* memoization이 아닌 recursive call을 사용하면 시간초과입니다.

#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;

int min3(int a, int b, int c) {
	if (a < b && a < c)
		return a;
	else
		if (b < c)
			return b;
		else
			return c;
}


int make_one(int n) {
	vector<int> arr(n + 1);
	int a = n;
	int b = n;
	int c = n;

	arr[1] = 0;
	for (int i = 2; i <= n; i++) {
		a = b = c = n;
		//a=n-1을 1로 만드는 횟수
		//b=n/3을 1로 만드는 횟수
		//c=n/2를 1로 만드는 횟수
		a = arr[i - 1];
		if (i % 3 == 0)
			b = arr[i / 3];
		if (i % 2 == 0)
			c = arr[i / 2];
		arr[i] = min3(a, b, c) + 1;
	}
	return arr[n];
}

int main() {
	int n;
	scanf("%d", &n);
	printf("%d\n", make_one(n));
}