[백준/BOJ] 백준 1463번 : 1로 만들기

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

1463번: 1로 만들기

정수 n이 3으로 나누어 떨어진다면 3으로 나누는 연산, 2로 나누어 떨어진다면 2로 나누는 연산, 1을 빼는 연산 중에서 연산된 값의 1을 만드는 데 사용되는 연산의 사용 횟수가 최소인 것을 고르면 정수 n이 1을 만드는 데 사용되는 연산의 최소 횟수를 구할 수 있다. cache를 사용해 이미 계산된 값은 중복해서 다시 계산하는 것을 방지하였다.

 

코드

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int cache[1000001];

int solve(int n)
{
	int& ret = cache[n];

	//ret가 -1이 아니라면 계산했던 값이므로 그 값을 리턴한다
	if (ret != -1)
		return ret;

	//기저 사례 (1을 만들었다면 더 이상 연산을 하지 않는다)
	if (n == 1)
		return 0;

	//3으로도 나누어 떨어지고, 2로도 나누어 떨어지면
	//3로 나누는 연산, 2로 나누는 연산, 1을 빼는 연산 중 계산된값의 연산사용 횟수가 최소인 것을 고른다. + 1 하는것은 해당 연산이다
	if (n % 3 == 0 && n % 2 == 0)
	{
		ret = min(solve(n / 3) + 1, solve(n / 2) + 1);
		ret = min(ret, solve(n - 1) + 1);
	}

	//2로 나누어 떨어지지 않고 3으로 나누어 떨어지면
	//3로 나누는 연산, 1을 빼는 연산 중 계산된값의 연산사용 횟수가 최소인 것을 고른다. + 1 하는것은 해당 연산이다
	else if (n % 3 == 0)
	{
		ret = min(solve(n / 3) + 1, solve(n - 1) + 1);
	}

	//3으로 나누어 떨어지지 않고 2로 나누어 떨어지면
    //2로 나누는 연산, 1을 빼는 연산 중 계산된값의 연산사용 횟수가 최소인 것을 고른다. + 1 하는것은 해당 연산이다
	else if (n % 2 == 0)
	{
		ret = min(solve(n / 2) + 1, solve(n - 1) + 1);
	}

	//3으로 나누어 떨어지지 않고, 2로도 나누어 떨어지지 않으면
	//1을 뺀 연산을 한다. + 1 하는것은 해당 연산이다
	else
	{
		ret = solve(n - 1) + 1;
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	//cache를 -1로 초기화 한다
	memset(cache, -1, sizeof(cache));

	int n;
	int result;

	cin >> n;
	result = solve(n);

	cout << result;

	return 0;
}