백준(BOJ) 1463번 1로 만들기

안녕하세요? 오늘은 백준 알고리즘 사이트의 문제 중 하나인 1463번 '1로 만들기'를 풀어보려 합니다.

문제 부터 보시겠습니다.

문제의 핵심은 주어진 3개의 연산을 사용하여 N을 1로 만들수 있는 최소의 연산 개수를 구하라는 것인데요?

어떻게 풀면 좋을까요?? 

먼저 문제의 감을 잡기 위해 하나씩 써보겠습니다. 

입력이 1일 때, 연산의 횟수는 0입니다.

입력이 2일 때, 연산의 횟수는 -1을 하면 되므로 1입니다. 또는 /2를 해도 1입니다.

입력이 3일 때, 연산의 횟수는 /3을 하면 되므로 1입니다.

입력이 4일 때, 연산의 횟수는 -1하면 3이고 이를 /3 해주면 되므로 2입니다. 또는 /2를 하여 2를 만든 다음, -1를 빼줘도 2이고, /2를 하여 2를 만든 다음 /2를 해도 2입니다.

자, 이제 어느정도 감이 잡히셨나요? 우리가 입력 4를 계산할 때, 앞에서 이미 풀어놓았던 문제(입력3과 2)를 반복하게 되죠?? 이런 경우에 효과적으로 연산을 진행할 수 있는 알고리즘이 있는데 바로 다이나믹 프로그래밍(Dynamic programming)입니다.

어떤 N이 주어졌을 때, 가능한 연산 3개를 모두 사용하는데, 이때 가장 최소 횟수의 연산을 기록하여 다음에 이용하는 것입니다. 그리고 입력의 최소값부터 최대값까지 차례로 올라가면서 작은 문제를 풀며 이를 활용하여 이후에 더 큰 문제를 해결해나가는 방식으로 풀 것입니다.

[소스코드]

#include <iostream>
#include <algorithm>
#include <cstring>
#define SIZE 1000001
#define INF 2e9
int DP[SIZE];

void preprocessing() 
{
	int moduloBy2 = 0;
	int moduloBy3 = 0;
	DP[0] = 0; DP[1] = 0; DP[2] = 1; DP[3] = 1;
	for (int idx = 4; idx < SIZE; idx++)
	{
		moduloBy2 = INF;
		moduloBy3 = INF;
		if (idx % 2 == 0) {
			moduloBy2 = DP[idx / 2];
		}
		if (idx % 3 == 0) {
			moduloBy3 = DP[idx / 3];
		}
		DP[idx] = std::min({ DP[idx - 1], moduloBy2, moduloBy3 }) + 1;
	}
}

int main() 
{
	int N;

	std::cin >> N;

	preprocessing();

	std::cout << DP[N] << std::endl;
	return 0;
}

코드를 보시면 preprocessing() 함수에서 나올 수 있는 최소값부터 최대값을 미리 계산해놓고 입력으로 N에 해당하는 최소 연산의 횟수를 출력하도록 하였습니다.

좀 더 효율적으로 preprocessing을 하려면 백만까지 구하지 말고 입력받은 N까지만 구하도록 하면 속도 측면에서 좀 더 향상될 것입니다.