[알고리즘/DP] 백준 1463번: 1로 만들기 - C++

www.acmicpc.net/problem/1463

1463번: 1로 만들기

다이나믹 프로그래밍을 이용하였다.

#include  <iostream>
using namespace std;
int d[1000001];
int main() {
	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] > d[i/2] + 1) {
			d[i] = d[i / 2] + 1;
		}
		if (i % 3 == 0 && d[i] > d[i / 3] + 1) {
			d[i] = d[i / 3] + 1;
		}
	}
	cout << d[N] << endl;
}

 

github.com/waves123/1463/blob/master/1463/1463.cpp

waves123/1463

 

다이나믹 프로그래밍 문제

2020/12/12 - [알고리즘] - [알고리즘/DP] 백준 1912번: 연속합 - C++

2020/12/12 - [알고리즘] - [알고리즘/DP] 백준 11055번: 가장 큰 증가 부분 수열 - C++

2020/12/12 - [알고리즘] - [알고리즘/DP] 백준 11052번: 카드 구매하기 - C++

2020/12/12 - [알고리즘] - [알고리즘/DP] 백준 9095번: 1,2,3 더하기 - C++

2020/12/12 - [알고리즘] - [알고리즘/DP] 백준 11726번: 2xn 타일링 - C++

2020/12/12 - [알고리즘] - [알고리즘/DP] 백준 1463번: 1로 만들기 - C++