[백준] 1463번 : 1로 만들기

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 다이나믹 프로그래밍 문제로, 1부터 n까지 올라가면서 해당 수에서 1까지 가기 위한 최소 연산 횟수를 dp에 저장하는 Bottom-Up 방식으로 풀었다.

1) 1로 만들기 위한 목표 수인 n을 입력 받는다.

2) dp 배열을 1부터 n까지 갱신한다.

• dp[i]에는 i에서 시작해서 1까지 도달하기 위한 연산의 최소 횟수가 저장된다.
  • 3으로 나누거나, 2로 나누거나, 1을 빼거나 총 3가지의 연산이 가능하다.
  • i에서의 최소 연산 횟수 = i에서의 연산 1회 + i에서 연산 결과 나온 수일 때의 최소 연산 횟수
  • 따라서 점화식 : dp[i] = min(dp[i / 3], dp[i / 2], dp[i - 1]) + 1
• dp[1]은 0으로 초기화
• dp[2]부터 해당 점화식을 적용해 dp 갱신.
  • 3으로 나누거나 2로 나누는 연산은 해당 수가 3이나 2로 나누어 떨어질 때만 가능하므로 항상 가능한 연산인 1 빼기 연산(dp[i - 1])을 기본적으로 적용하고, 이후 조건을 통과할 때만 3으로 나눈 경우(dp[i / 3])와 2(dp[i / 2])로 나눈 경우와 비교하여 가장 작은 수일 경우를 dp[i]로 갱신한다.

3) 위 과정이 끝나면 dp[n]을 출력한다.

🖥️ 풀이 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;
int dp[10000001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int n;
	cin >> n;

	for (int i = 2; i <= n; i++)
	{
		dp[i] = dp[i - 1] + 1;
		if (i % 2 == 0)
			dp[i] = min(dp[i], dp[i / 2] + 1);
		if(i % 3 == 0)
			dp[i] = min(dp[i], dp[i / 3] + 1);
	}
	cout << dp[n];
}