문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
예제 입력 1
6
10 20 10 30 20 50
예제 출력 1
4
출처
- 문제를 만든 사람: baekjoon
- 데이터를 추가한 사람: harinboy
비슷한 문제
- 11054번. 가장 긴 바이토닉 부분 수열
- 11055번. 가장 큰 증가하는 부분 수열
- 11722번. 가장 긴 감소하는 부분 수열
- 12015번. 가장 긴 증가하는 부분 수열 2
- 12738번. 가장 긴 증가하는 부분 수열 3
- 14002번. 가장 긴 증가하는 부분 수열 4
- 14003번. 가장 긴 증가하는 부분 수열 5
알고리즘 분류
- 다이나믹 프로그래밍
풀이
이것은 간단한 원리로 구현을 할 수 있다.
- 각 인덱스를 순회를 돈다
- 현재 인덱스보다 이전에 놓여있으면서 그 값이 지금 인덱스보다 작으면 길이를 1 증가
최종적으로 나온 길이들 중 최댓값을 찾고, 1을 더하며 바로 정답이다. 1을 더하는 까닭은 입력이 없는 경우가 문제에서 없으니 길이가 0인 경우가 없기 때문이다. 이것들을 기반하여 코드를 작성해 보자. 보다 나은 수준의 설명은 아래로 내려서 관련 문서에서 상자 비유로 확인해 보도록 하자.
코드
#include <stdio.h>
#include <stdlib.h>
#define MAX(x, y) ((x) > (y)) ? (x):(y)
int main() {
int N;
scanf("%d", &N);
int *A = calloc(N, sizeof(int));
int *DP = calloc(N, sizeof(int));
for(int i = 0; i < N; i++) scanf("%d", A + i);
for(int k = 0; k < N; k++) {
for(int i = 0; i < k; i++) {
if(A[i] < A[k]) DP[k] = MAX(DP[i] + 1, DP[k]);
}
}
int result = 0;
for(int i = 0; i < N; i++) {
result = MAX(result, DP[i]);
}
result++; // minimum: 1
printf("%d", result);
return 0;
}