[C++] 백준 1463번: 1로 만들기

1463번: 1로 만들기

1463번: 1로 만들기

개요

이 문제는 "다이나믹 프로그래밍" 알고리즘으로 분류돼 있다.

관련하여 찾아보니, 재귀함수를 활용하는 것과 많이 비교된다.

한 번 계산한 것은 다시 계산하지 않는 것이 목표인 것이다.

이 문제에서도 마찬가지다.

틀린 풀이

어떤 수 X가 3으로 나누어 떨어지면, X / 3에 대한 계산은 이미 저장돼 있을 것이라 기대할 수 있다.

만약 X == 10일 경우, X가 2로 나누어 떨어지지만 2로 나누기 시작하여 1로 만드는 것보다 1을 뺀 이후 3으로 나누는 것이 더 적은 횟수의 연산을 할 수 있음을 알 수 있다.

따라서, X가 2 또는 3으로 나누어 떨어진다면, X - 1일 때의 연산 횟수와 X / 2(또는 X / 3)일 때의 연산 횟수 중 더 작은 횟수에 1을 더하면 된다.

X가 1일 때부터 3일 때 까지는 각각 [0, 1, 1]으로 정해져 있다.

이후 숫자에 대해서만 위에 기술한대로 적용하여 배열에 저장해 나가면된다.

코드는 다음과 같다.

#include <cstdio>

int main() {
	int X, count = 0;
	scanf("%d", &X);
	int* DP = new int[X];
	for (int num = 1; num <= X; num++) {
		if (num == 1)
			DP[num - 1] = 0;
		else if (num == 2 || num == 3)
			DP[num - 1] = 1;
		else if (num % 3 == 0)
			DP[num - 1] = (DP[num / 3 - 1] < DP[num - 2] ? DP[num / 3 - 1] : DP[num - 2]) + 1;
		else if (num % 2 == 0)
			DP[num - 1] = (DP[num / 2 - 1] < DP[num - 2] ? DP[num / 2 - 1] : DP[num - 2]) + 1;
		else
			DP[num - 1] = DP[num - 2] + 1;
	}
	printf("%d\n", DP[X - 1]);
	delete[] DP;
	return 0;
}

옳은 풀이

위 풀이는 당시(20년 9월)에는 정답 처리가 됐지만, 이후(21년 1월)에 재채점 되면서 틀린 풀이가 됐다.

다이나믹 프로그래밍으로 분류된 문제를 풀면서 가장 바람직한 태도는 𝙨𝙞𝙢𝙥𝙡𝙚 𝙞𝙨 𝙗𝙚𝙨𝙩이다.

위 풀이에서 처럼 조건이 많이 붙을 수록 생각하지 못 한 반례가 생기기 쉽다.

이 문제를 간단히 생각하면 다음 중 최소값이다.

1. K가 3으로 나누어 떨어지는 경우 K / 3번째 값 + 1

2. K가 2로 나누어 떨어지는 경우 K / 2번째 값 + 1

3. K - 1번째 값 + 1

이를 코드로 나타내면 아래와 같다.

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int N;
	cin >> N;

	vector<int> DP(N + 1, INF);

	DP[1] = 0;
	DP[2] = 1;
	DP[3] = 1;
	for (int i = 4; i <= N; ++i) {
		if (i % 3 == 0)
			DP[i] = DP[i / 3] + 1;
		if (i % 2 == 0)
			DP[i] = min(DP[i], DP[i / 2] + 1);
		DP[i] = min(DP[i], DP[i - 1] + 1);
	}

	cout << DP[N] << EL;

	return 0;
}

제출 결과