[백준 / C++] 1로 만들기(실버3, 1463)

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

문제

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

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

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

입력

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

출력

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

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

---

문제 풀이

이번 문제는 대표적인 DP 문제입니다.

 

N의 범위는 1 ~ 1,000,000이며 모든 경우에서의 최솟값을 구해야 하므로 최솟값을 업데이트해가며, 최솟값보다 큰 경우는 전부 반환시켜줘야 합니다.

 

1부터 차례대로 올라가는 방식도 존재하지만, 저의 경우 재귀를 통해 아래로 내려가는 Top-Down 방식으로 로직을 구현하는 것이 익숙하기에 재귀를 사용해 이번 문제를 해결하게 되었습니다.

코드

#include <iostream>

using namespace std;

int n;
int DP[1000000];

void Go(int num, int cnt)
{
	if (DP[1] != 0 && DP[1] < cnt) return;

	if (num == 1 && DP[num] <= cnt)
	{
		DP[num] = cnt;
		return;
	}

	if (DP[num] != 0 && DP[num] <= cnt) return;

	DP[num] = cnt;

	if (num % 3 == 0) Go(num / 3, cnt + 1);
	if (num % 2 == 0) Go(num / 2, cnt + 1);
	Go(num - 1, cnt + 1);
}

int main()
{
	cin >> n;

	Go(n, 0);

	cout << DP[1];
}