BOJ - 1463번_1로 만들기 (C++)

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 할 때, 연산을 사용하는 횟수의 최솟값을 출력하는 프로그램 작성하기

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

• X가 3으로 나누어 떨어지면, 3으로 나눈다.

• X가 2로 나누어 떨어지면, 2로 나눈다.

• 1을 뺀다.

풀이

DP를 이용한다.

D[i] = i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값을 구해야 한다.

점화식을 생각해보면 d[k]는 3으로 나누어 떨어지면 d[k]=d[k/3]+1, 2로 나누어 떨어지면 d[k]=d[k/2]+1, 1을 빼면 d[k]=d[k-1]+1 중 최솟값임을 알 수 있다.

소스코드

#include <iostream>
using namespace std;

int d[1000001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int N;
	cin >> N;
	
	d[1] = 0;
	for(int i=2; i<=N; i++) {
		d[i] = d[i-1]+1;
		if(i%2==0) {
			d[i] = min(d[i], d[i/2]+1);
		}
		if(i%3==0) {
			d[i] = min(d[i], d[i/3]+1);
		}
	}
	cout << d[N];
}