[1463] C++ : 1로 만들기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

문제

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

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

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

입력

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

출력

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

예제 입력 

2

예제 출력 

1

예제 입력 

10

예제 출력 

3

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

 

풀이

다이나믹 프로그래밍 기법을 사용하여 해결한 첫 문제이다. 다이나믹 프로그래밍에 대해 간략하게 서술하자면, 메모리를 효과적으로 사용하기 위해서 탄생한 기법으로 이미 계산된 문제는 다시 해결하지 않게 알고리즘을 짜는 것이다. 

다이나믹 프로그래밍 방식은 두 가지로 나누어져 있다. 

1. bottom - up

2. top - down 

이에 대한 자세한 설명은 내가 글로 하는 것 보다 아래 유튜브 영상이 더 친절하게 설명해주고 있으니 참고하길 바란다. 

https://www.youtube.com/watch?v=5Lu34WIx2Us 

 

다이나믹 프로그래밍을 이용해 문제를 풀어보겠다.

이 문제가 다이나믹 프로그래밍이 필요한 이유는 만약 10을 1로 만들고자 하면 1을 뺀 값인 9와 2로 나눈 값인 5 중 어떤 수가 더 적은 수로 만들 수 있는지 알아야한다. 그리고 9랑 5도 구해야하고 계속 재귀적으로 들어가야한다. 이렇게 생각하면 너무 머리도 아프고 계산도 많아진다. 그래서 bottom-up 방식을 이용해 아래서부터 하나씩 쌓아나가서 원하는 수까지 도달한다면 정말 쉽게 구할 수 있다. 

 

1로 만들기 위한 최소 숫자를 배열에 넣는다고 생각해보자. 어떤 수 i 에 대하여 (i >=4 ) arr[i]를 구할 때는 arr[i-1]의 값과 arr[i/2]의 값(i %2 == 0일 때만) 과 arr[i/3]의 값 (i %3 == 0일 때만)의 값을 비교해 가장 작은 값에 +1을 하면 된다. 

 

<최종 코드>

#include<iostream>
#define MAX 1000000

int arr[MAX] = { 0 };

void makeOne(int n)
{
	int a, b, c;
	arr[1] = 0;
	arr[2] = 1;
	arr[3] = 1;
	for (int i = 4; i <= n; i++)
	{
		a = MAX, b = MAX, c = MAX;
		if (i % 2 == 0)
			a = arr[i / 2];
		if (i % 3 == 0)
			b = arr[i / 3];
		c = arr[i - 1];
		if (a > b)
		{
			if (b > c)
				arr[i] = c;
			else
				arr[i] = b;
		}
		else
		{
			if (a > c)
				arr[i] = c;
			else
				arr[i] = a;
		}
		arr[i] += 1;
	}
}

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

	makeOne(n);
	printf("%d", arr[n]);

}