728x90
dp
-
[알고리즘/DP] 백준 1463번: 1로 만들기 - C++알고리즘/백준 2020. 12. 12. 21:49
www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 다이나믹 프로그래밍을 이용하였다. #include using namespace std; int d[1000001]; int main() { int N; cin >> N; d[1] = 0; for (int i = 2; 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