💡 다이나믹 프로그래밍
Memory 1120KB Time 0ms Code Length 462B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<stdio.h>
#define max(x,y) x>y?x:y
int arr[1001];
int memo[1001];
int dp(int n) {
for (int i = 0; i < n; i++) {
memo[i] = 1;
for (int j = 0; j < i; j++) {
if (arr[j] > arr[i]) memo[i] = max((memo[j] + 1), memo[i]);
}
}
int result = 0;
for (int i = 0; i < n; i++) {
result = max(result, memo[i]);
}
return result;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf(" %d", &arr[i]);
}
printf("%d", dp(n));
}
이 코드는 주어진 배열에서 가장 긴 감소하는 부분 수열의 길이를 구하는 프로그램이다.
dp 함수는 배열을 순회하면서 각 요소에서 가장 긴 감소하는 부분 수열의 길이를 계산한다.
memo 배열은 각 요소에서의 가장 긴 감소하는 부분 수열의 길이를 저장한다.
memo[i]는 i번째 요소까지의 가장 긴 감소하는 부분 수열의 길이를 나타낸다.
두 번째 for 루프에서는 현재 요소보다 작은 이전 요소들을 확인하면서 memo[i]를 업데이트한다.
main 함수에서는 배열의 크기와 요소들을 입력받고 dp 함수를 호출하여 결과를 출력한다.
