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

1463번: 1로 만들기

 

📄 문제

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

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

📝 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> dp(1000001);

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

	dp[1] = 0;

	// bottom-up
	for (int i = 2; i <= N; ++i)
	{
		// 1을 더해보기
		dp[i] = dp[i - 1] + 1;

		// 3으로 나누어 떨어진다면, 현재 값과, 3으로 나누고 + 1한 값 중 낮은 값을 사용
		if (i % 3 == 0)
			dp[i] = min(dp[i], dp[i / 3] + 1);

		// 2로 나누어 떨어진다면, 현재 값과, 2로 나누고 + 1한 값 중 낮은 값을 사용
		if (i % 2 == 0)
			dp[i] = min(dp[i], dp[i / 2] + 1);
	}

	cout << dp[N];
}

• bottom-up 방식으로 문제를 해결합니다.
• dp[1]은 0이므로, 2부터 시작하여 차례대로 최소값을 갱신하여 나아갑니다.
  • 단순히 이전 값에서 1을 더하여 계산합니다.
  • 만약 3으로 나누어 떨어진다면, 현재 값과 3으로 나누고 1을 더한 값 중 낮은 값을 사용합니다.
  • 만약 2로 나누어 떨어진다면, 현재 값과 2로 나누고 1을 더한 값 중 낮은 값을 사용합니다.