이해 단계
수열 문제 시리즈이다.
수열이 주어질 때 증가하는 부분 수열을 원소들을 찾는다.
그 원소들의 집합 중 합이 가장 큰 집합을 찾아 그 값을 찾아내는 문제이다.
문제 접근 단계
가장 큰 수열 ~ 문제 시리즈 상 문제를 읽지 않아도
DP로 풀어야겠구나라고 생각이 바로 들더라..
이러면 안 되긴 하는데 너무 문제가 시리즈상으로 많이 있어서 자연스럽게 그렇게 됐다..
그래도 이 문제가 왜 DP로 풀 수 있는지 따져보기로 했다.
이 문제의 예제로 살펴보도록 하자.
{1, 100, 2, 50, 60, 3, 5, 6, 7, 8}
왼쪽부터 x = 1이라고 해서 순차적으로 올라가 보면서 생각해 보겠다.
x = 1 일 때 최댓값은 1이다.
x = 2 일 때, (1)(1+100)(100) 중, 최댓값은 101이다.
x = 3 일 때 값은 2이기 때문에
증가값이 되기 위해서는 값이 2보다는 낮아야 한다.
따라서 100을 제외하고 (1+2)인 3이 최댓값이다.
x = 4 일 때도 같은 원리로 100을 제외하고 1과 2만 가능하다.
그중 제일 큰 값을 구해보면 (50+2+1)인 53이 최댓값이 된다.
여기까지 살펴봤을 때 특징을 살펴보면,
증가하는 수열이 되기 위해서는 현재 기준이 되는 x의 값보다 작아야만 한다.
그리고 x = 4 일 때를 생각해 보자.
(50 + 2+ 1)에서 (2+1)은 사실 x = 2 일 때의 최댓값이다.
즉 부분의 답이 전체의 답이 되기 때문에 DP라고 할 수 있는 것이다.
이 사실을 x로 일반화해 보면 이렇게 된다.
수열에서 인덱스 X의 최댓값을 DP(X)라고 했을 때,
DP(X)는 DP(1)~DP(X-1) 중에 최댓값에 X값을 더한 값을 더한 것이 최댓값이다.
이를 이제 코드로 구현해 보도록 하겠다.
문제 구현 단계
#include <iostream>
using namespace std;
int d[1001];
int v[1001];
int main(){
cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> v[i];
int ans = 0;
for(int i = 1; i <= n; i++){
d[i] = v[i];
for(int j = 1; j < i; j++){
int val = v[i];
if(v[i] > v[j]){
d[i] = max(d[i],v[i]+d[j]);
ans = max(ans,d[i]);
}
}
ans = max(ans,v[i]);
}
cout << ans;
}각 인덱스 부분마다 최댓값을 담을 배열 d와
각 수열의 값인 x를 담을 배열 v를 선언했다.
이중 반복문을 이용했는데 첫 번째 반복문에서는 DP(X)를 의미하는 i를,
두 번째 반복문에서 DP(1) ~ DP(X-1)를 의미하는 j를 표현하였다.
i값이 j값보다 클 때만 비교를 하도록 하여 d [i] 값을 경신하도록 한다.
d [i] 값은 v [i] + d [j]의 값 중 가장 큰 값이 들어오도록 하고,
ans는 전체 값 중 가장 최댓값이 들어오도록 한다.
반복문 밖에 ans = max(ans, v [i]); 를 한번 더 해준 이유는
i값이 j값보다 큰 값이 하나도 없을 수도 있고
i값이 1일 때는 두 번째 반복문에 들어가지 않기 때문이다.
이렇게 하면 최댓값이 출력된다.
시행착오
이 시리즈 문제 자체는 익숙해서 로직은 금방 짰는데,
구현에서 오래 걸렸다. 나는 아직 구현 능력이 부족한가 보다.
프로그래밍 스킬이나 논리적인 생각이 부족한 거 같다.
좀 더 열심히 코딩해야 할 것 같다.