반응형
수열이 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 코드를 짜야한다!
10 | 20 | 10 | 30 | 20 | 50 |
1 | 2 | 1 | 3 | 2 | 4 |
방식은 우선 수열을 for문을 돈다. 그리고 맨 처음부터 해당 수까지 for문을 돌면서 자신보다 작은 아이가 있다면!
해당 dp의 수에 +1을 한 것과 현재 dp의 수를 비교하여 더 큰 값을 저장해준다. 그렇게 되면 앞에서 자기보다 작으면서 증가하는 부분 수열을 구할 수 있기 때문이다...
사실 이러한 방법은 처음 접해보는 방식이었기 때문에! ㅜㅠㅜㅠ 다른 포스팅들을 참고했다...! dp로 최소값과 최대값을 찾는게 왜인지 너무 어렵게 느껴진다... 반복학습 하다보면 익숙해질까아아~🙏
#include <iostream>
#include <vector>
using namespace std;
int arr[1001];
vector<int> dp(1001, 1);
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> arr[i];
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j])
dp[i] = max(dp[j] + 1, dp[i]);
}
}
int ans = 0;
for (int i = 0; i < n; i++)
ans = max(ans, dp[i]);
cout << ans << endl;
return 0;
}
반응형
'Algorithm 💫 > Problem Solving' 카테고리의 다른 글
[백준 11724번 연결 요소의 개수(BFS, DFS)/ C++] (0) | 2021.01.22 |
---|---|
[백준 2745번 진법 변환 / C++] (0) | 2021.01.21 |
[백준 2193번 이친수/ C++] (0) | 2021.01.07 |
[백준 11057번 오르막 수/ C++] (0) | 2021.01.07 |
[백준 10844번 쉬운 계단 수/ C++](DP) (5) | 2021.01.07 |
댓글