* memoization이 아닌 recursive call을 사용하면 시간초과입니다.
#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;
int min3(int a, int b, int c) {
if (a < b && a < c)
return a;
else
if (b < c)
return b;
else
return c;
}
int make_one(int n) {
vector<int> arr(n + 1);
int a = n;
int b = n;
int c = n;
arr[1] = 0;
for (int i = 2; i <= n; i++) {
a = b = c = n;
//a=n-1을 1로 만드는 횟수
//b=n/3을 1로 만드는 횟수
//c=n/2를 1로 만드는 횟수
a = arr[i - 1];
if (i % 3 == 0)
b = arr[i / 3];
if (i % 2 == 0)
c = arr[i / 2];
arr[i] = min3(a, b, c) + 1;
}
return arr[n];
}
int main() {
int n;
scanf("%d", &n);
printf("%d\n", make_one(n));
}
'코테 > DP' 카테고리의 다른 글
[java] 프로그래머스스쿨 연습문제 Lv.2 DP 문제 모음 (0) | 2023.04.28 |
---|---|
[C/C++] 백준 2775, Dynamic Programming (0) | 2022.12.10 |