Search
Duplicate
🍋

가장 긴 증가하는 부분 수열

주차
11
문제번호
11053
언어
티어
실버
유형
DP
nj_Blog
nj_상태
이해도
풀이
풀이 O
사람
이해도 2
13 more properties

Memo

1. 처음 생각 (틀렸음)

처음 이 문제를 생각할 때에는 첫번째 인덱스부터 max값을 바꿔가면서 큰 값을 찾아나가면 된다고 생각했다. 하지만 이번 문제에서는 아래와 같은 입력이 들어왔을때 출력을 고려해야 한다.
{20, 40, 1, 2, 3, 4}
즉 언제 어디서 가장 긴 증가하는 부분수열이 나올지 모르는 것이다.
따라서 DP배열을 사용해서 해당 문제를 접근하였다.

2. dp 적용하기

첫 시도는 방문한 인덱스에서 N까지 가면서 max값보다 큰 값이 나오면 result를 늘려주는 방식으로 구현하였다. 하지만 이렇게 하니 dp배열이 제대로 작동하지 않았다. 그래서 반대로 0에서 현재 방문한 인덱스까지 나보다 작은 칸의 개수를 세기로 하였다.
아래는 배열이 들어왔을 때, dp[3]을 구하는 방법이다.
루프를 통해 0 ~ N - 1(즉, 2)까지 돌면서 기존에 저장해 나가던 값과 해당 인덱스에서의 최대값을 비교해서 결과를 도출한다.

Code

제출 날짜

@2/23/2021

메모리

2016 KB

시간

0 ms
#include <iostream> #include <vector> int N; int result; std::vector<int> arr; std::vector<int> dp; void output() { std::cout << result; } void solution() { for (int i = 0 ; i < N ; i++) { for (int j = 0 ; j < i ; j++) { if (arr[i] > arr[j]) dp[i] = std::max(dp[i], dp[j] + 1); } result = std::max(result, dp[i]); } } void input() { std::cin >> N; arr.resize(N); dp = std::vector(N, 1); for (int i = 0 ; i < N ; i++) std::cin >> arr[i]; } void preset() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); } int main() { preset(); input(); solution(); output(); }
C++
복사