[백준] 11053 가장 긴 증가하는 부분 수열
2022. 5. 12. 12:47ㆍTIL💡/Algorithms
https://www.acmicpc.net/problem/11053
초기화를 잘못해서 어이없게 헤맨 문제이다.
처음에 코드를 짤 때 신중하고, 엣지 케이스를 잘 만들어야 한다.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n);
// 모든 수의 최소 길이는 1이므로 인덱스가 0인 값 외에도 1로 초기화해야 한다.
vector<long long> dp(n , 1);
for(int i = 0;i < n;i++) {
cin >> v[i];
}
long long ans = 1;
for(int i = 1;i < n;i++) {
for(int j = i - 1;j >= 0;j--) {
if(v[i] > v[j] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
if(dp[i] > ans) ans = dp[i];
}
}
}
cout << ans << '\n';
}
'TIL💡 > Algorithms' 카테고리의 다른 글
[중급 알고리즘] 분할 정복, 정렬 (0) | 2022.05.12 |
---|---|
[중급 알고리즘] 그리디 알고리즘 (0) | 2022.05.12 |
[프로그래머스] 정수 삼각형 (0) | 2022.05.12 |
[중급 알고리즘] BFS (0) | 2022.05.11 |
[알고리즘 중급] 비트마스크 (0) | 2022.05.10 |