728x90
처음 봤을 땐
"엥? 이거그냥 중복하면 받지말고 나중에 벡터 사이즈 넣으면 끝인데?" 라고 생각했다.
그런데 정답률이 낮아서 의아했다.
그리고 당연히 그런 문제가 아니었다. 이 문제의 가장 중요한 건 문제 해석을 완벽히 해야한다.. 이 문제의 이름을 잘 보자
" 가장 긴 -증가하는- 수열 "
그러니까 예를들어 5 4 3 2 1 이라는 순서로 들어왔을 때 그냥 1 2 3 4 5라고 생각할 수 있지만 이 문제는 "수열" 이다. 순서를 절대 바꾸면 안된다. 그러므로 증가하는 부분 수열의 길이는 1이다. 이 문제는 들어오는 숫자가 과연 증가하는 수열을 만들수 있는가? 물어보는 문제이다.
- 예를 들어보자!
5 2 4 3 2 순으로 들어왔다고 가정하자.
1) 5가 들어왔을 때 -> 아무것도 없고 처음이므로 증가 하는 부분 수열은 1이다. DP[5] = 1
2) 2가 들어왔을 때 -> 5가 있지만 5 ,2 는 증가 수열이 아니므로 DP[2] = 1
3) 4이 들어왔을 때 -> 5 2 4 에서 4보다 작은 수가 1개 있으므로 DP[4] = 2
4) 3이 들어왔을 때 -> 5 2 4 3 에서 3보다 작은 수는 1개 있으므로 DP[3] = 2
5) 2가 들어왔을 때 -> 5 2 4 3 2 에서 2보다 작은 수는 1개 있으므로 DP[2] = 1
그러므로 여기서 가장 긴 증가하는 수열은 2가 된다.
여기서 DP 갱신 조건은 원소 A가 들어오고 인덱스 0부터 살펴봤을 때 A보다 작은 게 있다면 DP + 1 을 해주면 된다.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
int n, m;
int DP[1001] = { 0, };
vector<int> vec;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> m;
vec.push_back(m);
DP[m] = 1;
}
int answer = 0;
for (int i = 0; i < vec.size(); i++) {
for (int j = 0; j < i; j++) {
if (vec[i] > vec[j]) {
DP[vec[i]] = max(DP[vec[j]] + 1, DP[vec[i]]);
}
}
answer = max(answer, DP[vec[i]]);
}
cout << answer << endl;
}
'백준 문제 풀이' 카테고리의 다른 글
백준 11055 가장 큰 증가 부분 수열(C++) (1) | 2022.12.27 |
---|---|
백준 1932 정수 삼각형(C++) (0) | 2022.12.27 |
백준 1076 저항(C++) (0) | 2022.12.17 |
백준 13913번 숨바꼭질 4 (C++) (0) | 2022.12.12 |
백준 17070번 파이프 옮기기 1(C++) (1) | 2022.12.12 |