💡 다이나믹 프로그래밍
Memory 1112KB Time 0ms Code Length 479B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<stdio.h>
#define max(x,y) x>y?x:y
int score[301] = { 0 };
int memo[301] = { 0 };
int dp(int n) {
memo[1] = score[1];
memo[2] = score[1] + score[2];
memo[3] = max(score[1] + score[3], score[2] + score[3]);
for (int i = 4; i <= n; i++) {
memo[i] = max(memo[i - 3] + score[i - 1] + score[i], memo[i - 2] + score[i]);
}
return memo[n];
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf(" %d", &score[i]);
}
printf("%d", dp(n));
}
이 코드는 n개의 숫자를 입력받아서 이를 배열 score에 저장한 후, dp 함수를 통해 최대 점수를 계산하는 프로그램이다. dp 함수는 Bottom-Up 방식으로 동적 계획법을 이용하여 최적해를 구한다. 먼저 memo 배열에 초기값을 설정한 후, 반복문을 통해 이전 단계의 값들을 활용하여 현재 단계의 최대 점수를 계산한다. 마지막으로 dp 함수에서 계산된 최대 점수를 출력한다.
