💡 다이나믹 프로그래밍
Memory 5016KB Time 4ms Code Length 406B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<stdio.h>
#define min(x,y) x>y?y:x
using namespace std;
int memo[1000001] = {0};
int dp(int n) {
if (n == 1) {
return memo[n];
}
for (int i = 2; i <= n; i++) {
memo[i] = memo[i - 1] + 1;
if (i % 2 == 0) memo[i] = min(memo[i], memo[i / 2] + 1);
if (i % 3 == 0) memo[i] = min(memo[i], memo[i / 3] + 1);
}
return memo[n];
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", dp(n));
}
이 코드는 다이나믹 프로그래밍을 사용하여 주어진 수 n을 1로 만들기 위해 필요한 연산의 최솟값을 구하는 프로그램이다.
우선 memo 배열은 0으로 초기화되어 있고, dp 함수는 n이 1이 될 때까지 반복하여 memo 배열에 값을 저장한다. memo[i]는 i를 1로 만들기 위해 필요한 최소 연산 횟수를 나타낸다.
i가 2부터 n까지 반복하면서, memo[i]는 memo[i-1] + 1로 갱신되고, 만약 i가 2로 나누어 떨어지면 memo[i]와 memo[i/2] + 1 중 작은 값으로 갱신된다. 또한 i가 3으로 나누어 떨어지면 memo[i]와 memo[i/3] + 1 중 작은 값으로 갱신된다.
마지막으로 main 함수에서는 사용자로부터 n을 입력받고 dp 함수를 호출하여 최소 연산 횟수를 구한 후 출력한다.
