1463번 1로 만들기

문제 링크

1로 만들기

문제 풀이

N을 1로 만드는 최소 횟수를 $f(n)$ 이라고 하면, 점화식은 다음과 같다.

두번째 구현 코드는 1을 빼는 것보다 2나 3으로 나눌 수 있을 때는 나누는 것이 좋으므로 2나 3으로 나눈 나머지는 1을 뺀 상황이라고 생각하고 점화식을 세운다.

구현

#include <iostream> 
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
using ll = long long;

int cache[1000001];
int N;

int solve(int n) {
    if (n == 1) return 0;

    int& ret = cache[n];
    if (ret != -1) return ret;

    ret = solve(n - 1) + 1;
    if (n % 3 == 0) ret = min(ret, solve(n / 3) + 1);
    if (n % 2 == 0) ret = min(ret, solve(n / 2) + 1);
    
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    memset(cache, -1, sizeof(cache));
    cout << solve(N);
    return 0;
}

#include <iostream> 
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
using ll = long long;

int cache[1000001];
int N;

int solve(int n) {
	if (n < 2) return 0;

	int& ret = cache[n];
	if (ret != -1) return ret;

	ret = min(solve(n / 3) + n % 3 + 1, solve(n / 2) + n % 2 + 1);

	return ret;
}

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

	cin >> N;
	memset(cache, -1, sizeof(cache));
	cout << solve(N);
	return 0;
}