뭐라도 공부해보자!!( 이론 )/자료구조 및 알고리즘

백준 1463, 1로 만들기

잡학다식을꿈꾼다 2023. 11. 29. 16:07
반응형

문제

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

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

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

입력

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

출력

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

예제 입력 1 

2

예제 출력 1 

1

예제 입력 2 

10

예제 출력 2 

3

 

 처음에는 Greedy 방식으로 접근하였다. 3 으로 나누는 경우가 제일 좋고, 그 다음은 2 로 나누는 것, 마지막이 1 을 빼는 것을 반복하다면 최소한의 계산으로 1 을 만들 수 있을 것이라 생각했다. 그러나 막상 보니 항상 그렇지는 않다는 것을 알게되었다. (10 의 경우가 그러하다.)

 그러면 결국은 모든 경우에 대해서 따져 볼 필요가 있다는 것이다. 내가 생각해낸 방식은 역으로 1 부터 시작하여 1 을 더하거나, 2 를 곱하거나, 3 을 곱하는 경우를 노드로 하는 트리(tree)를 그려가는 것이었다. 그러다 한 노드가 입력받은 수와 같게되면 해당 노드의 레벨을 출력하였다. 이 방식은 정답을 얻기는 하였지만, 결과적으로 메모리 초과 문제를 불러왔다.

 코드는 다음과 같다.

 

#include <iostream>
#include <deque>

std::deque<std::pair<int, int>> cases;

int find_smallest_num(int to, int level) 
{
	
	if (to == 1) 
	{
		return 0;
	}

	cases.push_back({ 2, 1 });
	cases.push_back({ 3, 1 });

	
	while (!cases.empty()) 
	{
		int n = cases.size();

		for (int i = 0; i < n; i++)
		{
			if (cases.front().first == to)
			{
				return cases.front().second;
			}
			else
			{
				int toAdd[3] =
				{
					1 + cases.front().first,
					2 * cases.front().first,
					3 * cases.front().first
				};

				for (int j = 0; j < 3; j++)
				{
					if (toAdd[j] <= to)
						cases.push_back({ toAdd[j], cases.front().second + 1 });
				}

				cases.pop_front();
			}
		}
	}

	return -1;
}

int main() 
{
	int N;
	std::cin >> N;

	std::cout << find_smallest_num(N, 0);

	return 0;
}

 

 다르게 생각해보기로 하였다. 최소가 되는 경우는 무엇인가? 최소는 바로 전 단계의 최솟값에서 현재 단계의 최솟값을 더하는 것이다. 이게 무슨 말장난인인가 싶지만 실제로 유용한 문제 해결 방법이다. 나는 이 방법을 이용하여 다음과 같이 문제를 해결하였다.

 

  1. 입력을 받는다.
  2. 2 부터 시작하여 입력보다 작은 수에 대해 1 로 만드는 최소한의 연산 수를 연쇄적으로 구한다.
  3. N 을 1 로 만드는 최소한의 연산 수를 구한다.

 

코드는 다음과 같다.

 

#include <iostream>
#include <algorithm>

int min[1000000];

int main() 
{
	int N;
	std::cin >> N;

	for (int i = 2; i <= N; i++) 
	{
		min[i] = min[i - 1] + 1;

		if (i % 2 == 0) 
		{
			min[i] = std::min(min[i], min[i/2] + 1);
		}

		if (i % 3 == 0)
		{
			min[i] = std::min(min[i], min[i / 3] + 1);
		}
	}

	std::cout << min[N];

	return 0;
}

 

 이런 방식의 문제 해결방법을 다이나믹 프로그래밍(Dynamic Programming)이라 하는 데, 아직은 익숙하지 않은 것 같다. 이 부분은 더 많은 연습을 통해서 개선해 나갈 계획이다.

반응형