728x90
반응형
https://www.acmicpc.net/problem/11053
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
![](https://blog.kakaocdn.net/dn/HVAjS/btrUBbZ3205/5H5wl2ZUMFNFIdzssGLZ1K/img.png)
전에 풀어봤던 문제라서 쉽게 해결됐다
배열 a에 수열을 넣고 dp배열에는 i번째 값을 포함하는 가장 긴 수열의 수를 넣는다
dp배열은 1로 초기화하고
a값을 차례대로 비교하면서 자신의 값보다 작은 값의 dp값에 1을 더해준다
![](https://blog.kakaocdn.net/dn/bhqK8u/btrUyielPzE/lnr7xfB5yKznkA9RXQec7k/img.jpg)
#include <bits/stdc++.h>
using namespace std;
int n;
int dp[1001] = {0}, a[1001] ={0};
int main(void) {
cin >> n;
for(int i=1; i<=n; i++){
cin >> a[i];
dp[i] = 1;
}
dp[1] = 1;
for(int i=2; i<=n; i++){
for(int j=1; j<i; j++){
if(a[i]>a[j])
dp[i] = max(dp[i], dp[j]+1);
}
}
int result = 0;
for(int i=1; i<=n; i++){
result = max(result, dp[i]);
}
cout << result << endl;
return 0;
}
반응형
728x90
반응형
'알고리즘' 카테고리의 다른 글
[이코테/DFS&BFS/C++] DFS & BFS 기초 설명 및 예제 (0) | 2022.12.28 |
---|---|
[백준/DP/C++] 11052번 카드 구매하기 (0) | 2022.12.28 |
[백준/DP/C++] 9465번 스티커 (0) | 2022.12.27 |
[백준/DP/C++] 9461번 파도반 수열 (0) | 2022.12.26 |
[백준/DP/C++] 2193번 이친수 (0) | 2022.12.26 |