문제 이해 단계
수열이 주어졌을 때 위치를 가만히 둔 채로,
오름차순으로 증가하는 부분 수열은 구한다.
그때 가장 크게 증가하는 부분수열의 길이를 구하는 문제
문제 접근 단계
문제에 나와있는 예시로 생각해 보자
10 20 10 30 20 50
1번째 수(10)에서 가장 긴 부분수열의 길이는 1이다.
2번째 수까지의 경우의 수는 3가지이다.
1. 10 - 20 (2가지)
2. 20 (1가지)
3. 10 (1가지)
이때 가장 긴 부분수열은 1번째인 2이다.
3번째 수까지의 경우의 수는
1. 10 - 20 (2가지)
2. 20 - 10 (2가지)
3. 20
...
로 2번째보다 길어지려면 20보다 수가 높아야 하는데,
그렇지 못하므로 그대로 최대 길이는 2이다.
4번째 수까지의 경우의 수는
1. 10 - 20 - 30 (3가지)
2. 10 - 30 (2가지)
3. 20 - 30 (3가지)
...
로 1번째인 3이 가장 긴 길이이다.
여기까지 규칙을 보면 4번째 수 30은
자기보다 작은 수들의 부분수열 중 가장 길이가 긴 것에 +1을 한 것이다.
여기서 보면 10 - 20 - 30은
3번째까지 길이가 가장 길었던 경우의 수에 30을 붙인 것일 뿐이다.
이것을 우리는 일반화할 수 있다.
x까지의 부분수열의 최대길이는
x보다 작은 수들 중의 부분수열의 최대길이 + 1이다.
이것을 DP로 환원하여 계산식을 세워보면
DP [x] = MAX(DP [1~x-1])라고 할 수 있다.
자세한 것은 구현은 코드를 통해 설명하겠다.
문제 구현 단계
#include <iostream>
using namespace std;
int N;
int d[1001];
int v[1001];
int main() {
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> N;
for (int i = 1; i <= N; i++) cin >> v[i];
int ans = 1;
for (int i = 1; i <= N; i++) {
d[i] = 1;
for (int j = 1; j < i; j++) {
if (v[i] > v[j]) {
d[i] = max(d[i], d[j] + 1);
ans = max(ans, d[i]);
}
}
}
cout << ans;
}이중 반복문을 통해 DP를 구현하였다.
첫 번째 반복문에서 기준이 될 x를 정하고
두 번째 반복문에서 1~x-1까지를 반복해 max를 구한다.
j의 값이 i값보다 작을 때만 비교를 해주고 이것이 ans보다 클 때만 갱신해 준다.
이중 반복문으로 해당 문제를 풀 수 있는 이유는
N = 1000이기 때문에 1000 * 1000 = 10^6으로 1초가 넘어가지 않기 때문에 가능했다.
시행착오
굉장히 푸는데 난해하고 어렵던 문제였다.
3일 내내 고민하다가 방식을 여러 번 바꿔보고 해 봤는데도
전혀 안 풀려서 결국에는 인터넷을 참고할 수밖에 없었다.
DP를 항상 재귀함수로만 접근했었는데 이렇게 반복문으로도 접근할 수 있구나..
그리고 이렇게 내가 생각의 폭이 짧았구나.
잘못된 생각의 늪에 빠지니까 헤어날 수가 없어서
만약 아직까지 잡고 있었다면 여전히 못 풀었을 것 같다.
ㅠㅠ