https://www.acmicpc.net/problem/11053
문제
> 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
> 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.접근
dp를 사용해 수열의 크기별로 가능한 최대길이 수열 중 최대값을 구하고 최종적으로 n개의 각각의 dp중 제일 큰값을 고른다.
dp1은 첫번째 수를 마지막 수로 하여 구할 수 있는 수열들 중 최고많은 값이다. 근데 1은 수를 한개만 가지므로 1이다.
dp2는 두번째 수를 마지막으로 가지는 수열 즉 (1번쨰, 2번째)한개, (2번째)두개로 총 두개 가능하다.
근데 만약 1번째가 2번째 보다 큰 수라면 수열이 성립하지않아 (2번째)만 수열로 가질 수 있으므로 dp2는 1이 된다.
따라서 dpn을 구하려면 n을 끝으로 하는 수열 종류를 다 봐야하는데 n이전의 수가 n보다 크다면 볼 필요가 없고 n보다 작은 애들만 보면 된다.
예를 들어 dp6을 본다고 하면, 1부터 5까지의 수를 일단 6과 비교해서 6번째보다 작은 애들만 고려한다.(만약 1,2,4가 걸러졌다고 치자)
그럼 dp1과 dp2와 dp4중 큰 값을 고르고 거기에 6번쨰 수까지 수열에 추가해야하므로 +1 해주면 dp6이 나온다.
각각 1번째수, 2번째수, 4번째 수를 끝으로 한 수열 중 가능한 최고 긴 수열을 가지고 있기 떄문이다.
문제해결
> 수열의 크기 N을 입력받고 인덱스를 1부터 시작할것이므로 1부터 N+1크기의 수열을 입력받는다.
> dp를 담을 벡터도 1부터 시작하므로 N+1로 크기를 주고 초기값을 1로 설정한다. 각 dp는 최소한 자기 자신을 원소로한 수열을 1개씩은 가지고 있기 때문이다. 그리고 최대값을 구하기 위해 일단 최대값을 담을 rst의 값으로 dp[1]을 준다.
> 이제 dp[i]를 구하기 위해서 1부터 i-1번째 까지의 dp를 다봐야한다.이를 이중 반복으로 j를 i-1번째 까지 보도록 해준다.
> 현재 수 i에 대해 i보다 j가 작은 수들만 고려해야하므로 조건으로 걸러주고 걸러진 수들의 dp값 중 최대값을 구한다.
dp[i]가 1을 가지고있기 때문에 이를 초기값으로 dp[j]의 최조 값과 max연산을 해 j의 값을 전부 순회한다.
이때 dp[j]에 현재 수 i까지 수열에 추가한 수열의 길이를 dp[i]에 넣어야하므로 +1을 해준뒤 최대값을 구한다.
> dp를 구하면서 동시에 최종 결과를 유도한다.
현재 rst(최종 결과인 dp값중 가장 큰 값)에 dp[1]이 초기로 들어있고 dp[i]를 구하면서 rst와 max연산을 통해 최대값을 갱신한다.
> 위에서 최종적으로 rst에 들어있는 값을 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
vector<int> num(N+1);
for (int i = 1; i <= N; i++) cin >> num[i];
vector<int> dp(N+1, 1); //각 수는 자기 자신을 수열로 하는 최소의 1개 수열 가지고있음
int rst = dp[1];
for (int i = 1; i <= N; i++)
{
for (int j = 1; j < i; j++)
{
if (num[j] < num[i])
dp[i] = max(dp[i], dp[j] + 1);
}
rst = max(rst, dp[i]);
}
cout << rst << "\n";
}
후기
문제 이해부터 어려웠다. dp의 인덱스로 뭘 잡아야할지도 모르겠고, dp를 어떤 작은 값들로 유도해야할지도 도저히 몰라서 이 문제가 dp의 대표문제라길래 공부했다.
dp의 인덱스는 각각의 수를 끝수로 가지는 수열을 말하는 거로 푸는거라고 한다. 처음에 난 i를 시작으로 해서 마지막에 주어진 수까지의 수열 중 최고 길이를 구하는건줄 알았는데 완전 반대의 개념이었다.
이를 알고나니 훨씬 수월했다. 해당 i값 까지 보다 작은 번째 수들을 다 돌면 되니까이다.
여지껏 봤던 dp중 제일 어려웠던 문제가 아닐까 한다.
