반응형

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 가장 긴 증가하는 부분 수열 (11053)
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
[ 문제 ]
수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
[ 코드 ]
#include<iostream> #include<algorithm> #include<vector> using namespace std; int dp[1001]; // 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이(개수) int main() { int N; // 수열 A의 크기 cin >> N; vector <int> A(N); // 수열 A for (int i = 0; i < N; i++) { cin >> A[i]; // 수열 A를 이루고 있는 값, N개 입력 } for (int i = 0; i < N; i++) { dp[i] = 1; // 무조건 기본 값은 1이므로 초기화해두고 시작 for (int j = 0; j < i; j++) // for(int j=1 ; j<=i; j++)가 되면 안 됨. // 그 이유는 A[i] > A[i]라는 것은 비교가 무의미하기 때문 { if (A[i] > A[j] && dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; } } } int result = 0; for (int i = 0; i < N; i++) { result = max(dp[i], result); } cout << result; // vector <int> dp(1001)이라면 // cout<< *max_element(dp.begin(), dp.end()); 도 가능함 // 이는 주소값으로 반환되며, *max를 써야 함 return 0; }
반응형
'문과 코린이의, [C. C++] 기록 > C++ 백준 문제풀이' 카테고리의 다른 글
[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 연속합 (1912) (0) | 2021.07.22 |
---|---|
[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 가장 긴 증가하는 부분 수열[LIS] 4 (14002) (0) | 2021.07.22 |
[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 쉬운 계단 수 (10844) (0) | 2021.07.21 |
[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 이친수 (2193) (0) | 2021.07.21 |
[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 카드 구매하기 2 (16194) (0) | 2021.07.19 |