[백준] 1463_1로 만들기

[문제]: 1463번: 1로 만들기 (acmicpc.net)

 

숫자가 3의 배수 또는 2의 배수라고 바로 3, 2로 나누어서는 안 된다!

먼저 -1을 한 후의 연산 횟수가 더 적어질 수 있기 때문이다.

10을 예를 들어보면, 10은 2의 배수이니 2로 먼저 나눈다고 해보자. 아래 식은 괄호 없이 순서대로 계산한다(사칙연산 계산 순서 무시). 이때 연산 횟수는 총 4회.

\(10\div2-1\div2-1=1\)

하지만, 이렇게 계산할 수도 있다.

\(10-1\div3\div3=1\)

이때 연산 횟수는 총 3회.

따라서 주어진 숫자가 3의 배수 또는 2의 배수라 하더라도, 나누기하기 전에 먼저 -1을 한 연산 횟수와 비교를 해야 한다. 먼저 -1을 한 연산 횟수보다 작으면 나누기, 아니면 -1부터. 아래 코드에 if 조건을 보면 알 수 있다.

#include <iostream>
#include <vector>
using namespace std;

vector<int> dp(1000000, 0);
int NumOfOper(int n)
{
	dp[1] = 0, dp[2] = 1, dp[3] = 1;
	for (int i = 4; i <= n; ++i) {
		if ((i % 3 == 0) && (dp[i - 1] > dp[i / 3]))
			dp[i] = dp[i / 3] + 1;
		else if ((i % 2 == 0) && (dp[i - 1] > dp[i / 2]))
			dp[i] = dp[i / 2] + 1;
		else
			dp[i] = dp[i - 1] + 1;
	}
	return dp[n];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int N;
	cin >> N;
	cout << NumOfOper(N) << '\n';
	return 0;
}

 

 

다른 사람의 코드이다. 코드가 너무 이뻐서 참고하려고 가져왔다.

나머지 연산으로 -1 연산 횟수를 나타내는 부분을 유심히 보길.

#include <stdio.h>

int d(int n)
{
    int a, b;
    if (n <= 1)
        return 0;

    a = d(n / 2) + n % 2 + 1;
    b = d(n / 3) + n % 3 + 1;

    return (a < b) ? a : b;
}

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