https://www.acmicpc.net/problem/14002
14002번: 가장 긴 증가하는 부분 수열 4
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
www.acmicpc.net
아래 코드를 먼저 참고바랍니다.
https://coding-gongboo.tistory.com/38?category=829643
백준-가장 긴 증가하는 부분 수열 : 11053번 ( LIS)
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50..
coding-gongboo.tistory.com
11053번 문제는 수열의 길이만 구하면 되지만, 14002문제는 수열을 표현해 주어야 한다.
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
int n,i,a[1000]={0,},l[1000]={0,},j,ma=-1,k[1000]={0,},m;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(i=1;i<=n;i++)
{
l[i]=1;
k[i]=i;
for(j=1;j<i;j++)
{
if(a[j]<a[i])
{
//l[i]=l[i]>l[j]+1 ? l[i] : l[j]+1;
if(l[i] < l[j]+1)
{
l[i] = l[j]+1;
k[i]=j;
}
}
}
// ma=ma>l[i]?ma:l[i];
if(ma<l[i]){
ma=l[i];
m=i;
}
}
printf("%d\n",ma);
l[1] = a[m];
for(i=2;i<=ma;i++)
{
l[i]=a[k[m]];
m = k[m];
}
for(i=ma;i>0;i--)
printf("%d ",l[i]);
return 0;
}
'정보올림피아드-KOI > BOJ' 카테고리의 다른 글
| 백준 : 1로 만들기 1463번 (0) | 2020.02.09 |
|---|---|
| 백준 - 차이를 최대로 : 10819번 (0) | 2020.02.09 |
| 백준-가장 긴 증가하는 부분 수열 : 11053번 ( LIS) (0) | 2020.02.08 |
| 백준-부등호 : 2529번 (0) | 2020.01.15 |
| 백준 - 숨바꼭질 : 1697번 (0) | 2020.01.11 |