14002번: 가장 긴 증가하는 부분 수열 4
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
[난이도] Gold4
[유형] DP (LIS)
[풀이]
d[i] = i번째 수로 끝나면서 가장 긴 증가하는 부분수열의 길이
prev[i] = i번째 수로 끝나면서 가장 긴 증가하는 부분수열에서 i번째 앞의수 위의 두가지를 이용해서 구한다.
#include <cstdio>
int N,a[1001],d[1001],prev[1001];
void prt(int n){
if(n==0) return;
prt(prev[n]);
printf("%d ",a[n]);
}
int main(){
scanf("%d",&N);
for(int i=1;i<=N;i++) scanf("%d",&a[i]);
for(int i=1;i<=N;i++){
for(int j=0;j<i;j++){
if(a[j]<a[i]) {
if(d[i]<d[j]+1){
d[i]=d[j]+1;
prev[i]=j;
}
}
}
}
int mxi=0,mxV=0;
for(int i=1;i<=N;i++) {
if(d[i] > mxV){
mxi=i;
mxV=d[i];
}
}
printf("%d\n",mxV);
prt(mxi);
}github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/14002.cpp
'Problem-Solving > BOJ' 카테고리의 다른 글
| [BOJ/백준][Gold4] 16235 : 나무 재테크(C++) (0) | 2020.12.13 |
|---|---|
| [BOJ/백준][Gold4] 15685 : 드래곤 커브 (C++) (0) | 2020.12.13 |
| [BOJ/백준][Gold4] 13913 : 숨바꼭질4 (C++) (0) | 2020.12.13 |
| [BOJ/백준][Gold4] 1351 : 무한 수열 (C++) (0) | 2020.12.13 |
| [BOJ/백준][Gold4] 1339 : 단어 수학 (C++) (0) | 2020.12.13 |