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

✅ 문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

✅ 입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

✅ 출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

✅ 예제 입력 1

2

✅ 예제 출력 1

1

✅ 예제 입력 2

10

✅ 예제 출력 2

3

✅ 알고리즘 [ 접근 방법 ]

쉬운 형태의 다이나믹 프로그래밍 문제이다. 대부분 첫번째로 생각할 수 있는 문제풀이 방식은 다음과 같다.

1. 3으로 나누기
2. 2로 나누기
3. 1을 빼기

를 우선순위로 하여 주어진 수 N을 1로 만드는 방법이다. 그러나 해당 방법은 정답을 구할 수 없다.

간단한 예로 10을 들 수 있는데 위의 순서대로 10을 1로 만들면 10->5->4->2->1 총 4번의 과정이 필요하지만 10->9->3->1 과 같이 3번만에 1로 만드는 과정이 존재하므로 위의 우선순위는 틀리다.

따라서 DP방식으로 문제를 쪼개어 풀 필요가 있다.

DP문제를 풀 때에는 주어진 문제를 점화식으로 표현하는것이 첫번째이다.

D[N] = N을 1로만드는데 필요한 최소 연산 횟수라고 정의하자.

이때 N이 3으로 나누어 떨어질때 N을 3으로 나누는 과정을 살펴보면 N을 N/3으로 만들고 N/3을 1로 만드는 것이므로 1+D[N/3]이라는 점화식으로 표현가능하다.

마찬가지로 D[N/2]+1 , D[N-1]+1이라는 점화식을 만들어낼 수 있고 최종적으로

D[N] = min( D[N/3] , D[N/2] , D[N-1] ) +1 이라는 점화식을 산출할 수 있다.

이때의 시간복잡도 = 문제의 개수 X 문제 1개푸는데 걸리는 시간 이므로 T(N) = N X O(1) = O(N) 이다.

✅ 풀이1

#include <iostream>
using namespace std;

// Top-Down 방식

int D[1000000]; // D[N]을 1로 만드는데 필요한 연산 횟수

int func(int num) {

	if (num == 1) return 0; // D[1]인경우 0번연산하므로 
	if (D[num] > 0) return D[num]; // memoization

	D[num] = func(num - 1) + 1; // 아무때나 쓸수있는 비교대상 먼저 코드 작성

	if (num % 3 == 0) {
		int temp = func(num / 3) + 1;
		if (D[num] > temp) D[num] = temp;
	}

	if (num % 2 == 0) {
		int temp = func(num / 2) + 1;
		if (D[num] > temp)  D[num] = temp;
	}
	
	return D[num];
}

int main() {
	// cin의 연산시간을 scanf만큼 줄여주기 위한 코드 2줄
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int num;
	cin >> num;

	int res = func(num);
	cout << res;
}

✅ 풀이2

#include <iostream>
using namespace std;

// BottomUp 방식
int D[1000000];

int main() {
	// cin의 연산시간을 scanf만큼 줄여주기 위한 코드 2줄
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int num;
	cin >> num;

	D[1] = 0;

	for (int i = 2; i <= num; i++) {
		D[i] = D[i - 1] + 1;
		if (i % 3 == 0 && D[i] > D[i / 3] + 1)
			D[i] = D[i / 3] + 1;
		if (i % 2 == 0 && D[i] > D[i / 2] + 1)
			D[i] = D[i / 2] + 1;
	}

	cout << D[num] << endl;
}

✅ 알아두기

Q ) D[N/3]이나 D[N/2]가 아닌 D[N-1]부터 구현하는 이유는 뭘까?

A ) 문제가 최소값을 구하는 것이기 때문에 비교대상이 필요하다.

1. 3으로 나누어 떨어질때
2. 2로 나누어 떨어질때
3. 1로 뺄때

위의 1,2번 두개의 조건은 나누어 떨어질 때 라는 조건이 필요하지만 3번 조건은 어떤 수든지 상관없이 아무때나 사용 가능하다.

따라서 3번 조건을 먼저 코드작성을 해줘서 비교대상을 만들어준뒤 1,2번 조건을 구현하면 최솟값을 구할 수 있다.