https://www.acmicpc.net/problem/11053
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
www.acmicpc.net
이문제는 LIS(Longest Increasing Subsequence) 라는 유명한 문제입니다.
아래 코드는 다이내믹 방식으로 소스코드를 작성했습니다.
참고하시구요. 질문이나 수정할 부분있으면 알려주세요.^^
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
int n,i,a[100000]={0,},l[100000]={0,},j,ma=-1;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(i=1;i<=n;i++)
{
l[i]=1;
for(j=1;j<i;j++)
{
if(a[j]<a[i])
l[i]=l[i]>l[j]+1 ? l[i] : l[j]+1;
}
ma=ma>l[i]?ma:l[i];
}
printf("%d",ma);
return 0;
}'정보올림피아드-KOI > BOJ' 카테고리의 다른 글
| 백준 - 차이를 최대로 : 10819번 (0) | 2020.02.09 |
|---|---|
| 백준-가장 긴 증가하는 부분 수열 4 : 14002번 (LIS) (0) | 2020.02.08 |
| 백준-부등호 : 2529번 (0) | 2020.01.15 |
| 백준 - 숨바꼭질 : 1697번 (0) | 2020.01.11 |
| 백준 - 2×n 타일링 2 : 11727번 (0) | 2020.01.11 |