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

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

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

다이나믹 프로그래밍을 이용해서 푸는 문제
DP에 대한 개념이 거의 없는 상태였기 때문에 점화식을 세우는 부분에서 어려움을 겪었다 ㅠ_ㅠ

점화식 (Bottom-Up)

• f(1) = 0

1. X가 3으로 나누어 떨어질 때 f(X) = f(X/3) + 1
2. X가 2로 나누어 떨어질 때 f(X) = f(X/2) + 1
3. 그 외 f(X) = f(X-1) + 1

코드

오답 코드

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

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

	int N;
	cin >> N;

	// 연산 횟수를 저장하는 배열 생성
	vector<int> DP(N + 1);

	// 1일 경우 연산 횟수는 0회
	DP[1] = 0;
	
	// Bottom-Up 방식
	for (int i = 2; i <= N; i++) {
		if (i % 3 == 0) DP[i] = DP[i / 3] + 1;
		else if (i % 2 == 0) DP[i] = DP[i / 2] + 1;
		else DP[i] = DP[i - 1] + 1;
	}

	cout << DP[N];
}

점화식에 따라 코드를 작성했으나, 3이나 2로 나누어 떨어지더라도 1을 빼는 연산을 해야 최솟값이 구해지는 경우가 있기 때문에 추가적인 처리를 해주어야 했다

ex) 10->9->3->1

수정 코드

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

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

	int N;
	cin >> N;

	// 연산 횟수를 저장하는 배열 생성
	vector<int> DP(N + 1);

	// 1일 경우 연산 횟수는 0회
	DP[1] = 0;
	
	// Bottom-Up 방식
	for (int i = 2; i <= N; i++) {
		DP[i] = DP[i - 1] + 1;
		if (i % 3 == 0) DP[i] = min(DP[i], DP[i / 3] + 1);
		if (i % 2 == 0) DP[i] = min(DP[i], DP[i / 2] + 1);
		
	}

	cout << DP[N];
}

min 함수를 이용해 연산 횟수의 최솟값을 저장해주었다