🌈 백준 11053번 문제 소개

링크 : https://www.acmicpc.net/problem/11053

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 30, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4

🌈 DP로 문제를 풀어보자~!

☝️점화식 생각해보기!

어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분 수열을 만들 수 있다. 이때 만들어진 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 "최장 증가 부분 수열(Longest Increasing Subsequence)"이라고 한다. (나무위키)

예를 들어 {10, 20, 30, 10} 수열이 있을 때 최장 증가 부분 수열을 만들어보자.
만들어질 부분 수열이 오름차순이어야 한다.
DP 배열에는 현재 index까지 만들어진 최장 증가 부분 수열의 크기를 갱신한다.

index	0	1	2	3
수열	10	20	30	10
DP	1

index = 0일 때, {10}인 자기 자신 하나만 있기 때문에 부분 수열 값은 1이 된다. 따라서 DP = 1 이 된다.

index	0	1	2	3
수열	10	20	30	10
DP	1	2

index = 1일 때, {10, 20} 부분 수열이 되기 때문에 DP = 2가 된다.

index	0	1	2	3
수열	10	20	30	10
DP	1	2

index = 2일 때, {10, 20, 30} 부분 수열이 되기 때문에 DP = 3이 된다.

index	0	1	2	3
수열	10	20	30	10
DP	1	2	3	1

index = 3일 때, {10}보다 더 작은 값이 없기 이전에 때문에 부분 수열이 더 만들어지지 않는다. 자기 자신만 있으므로 DP = 1이다.
이렇게 이 수열의 최장 증가 부분 수열의 크기는 DP에서 제일 큰 값인 3이다.

i번 째 수열은 0번부터 i-1번의 수열까지 모두 검사하여
그 중에서 만들어지는 최장 증가 수열의 값을 DP에 갱신하여야 한다.
결국 2중 for문으로 구현하여 모두 검사해야 한다.

✌️ 코드로 구현하기!

이 문제의 가장 핵심 코드는 이렇게 나타낼 수 있다.

for(int i=0; i<n; i++){
	for(int j=0; j<n; j++){
    	//j번째 원소 값이 i번째 원소보다 작아야해
    	if(arr[i] > arr[j]){ 
        	//i번째 원소까지 추가한 부분 수열이 DP[i]보다 더 크다면 DP[i] 갱신
			dp[i] = max(dp[i] > dp[j]+1);
		}
    }
}

(1) if(arr[i] > arr[j])
i번째 원소 이전에 있는 j번째 원소들이 i보다 작은지 확인하는 단계이다.
만들어질 부분 수열은 항상 오름차순이어야 한다.
따라서 i번째 원소 값이 j번째 원소보다 클 때만 DP값이 갱신되는 것이다.

예를 들어
[10, 20, 30, 10]이 있다면
i = 3일 때 {10}이 추가되어 만들어질 부분 수열이 더이상 항상 증가하는 오름차순이 아니다.
더이상 DP를 갱신할 필요도 없으므로 if문으로 걸러주는 것이다.

(2) dp[i] = max(dp[i] > dp[j]+1)

i번째 원소를 마지막에 추가한 경우가 현재 DP[i]보다 크다면
i번째 원소를 포함하여 DP[i]를 갱신해야 하니 DP[i] = DP[j]+1 이다.

정리하면...
(1), (2) 두 조건을 모두 충족한다는 뜻은
(1) j번째 원소가 i번째 원소보다 작으면서
(2) i번째 원소를 마지막에 추가했을 때 부분 수열이 현재 DP[i] 보다 크다면
DP[j]+1하여 DP[i] 값을 갱신한다.

전체 코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> a, dp;
    int n;
    cin >> n;

    //n개의 원소로 이루어진 a수열을 vector로 만들기.
    for(int i=0; i<n; i++){
        int num;
        cin >> num;
        a.push_back(num);
    }

    //dp는 1로 초기화
    dp.assign(n, 1);

    //최장 증가 부분 수열 크기를 담을 정답 변수
    int ans = 0;
    
    //모든 데이터에 대해 검사하며 dp 갱신
    for(int i=0; i<n; i++){
        for(int j=0; j<i; j++){
            //j번째 원소는 항상 i번째 원소보다 작아야 된다. (LIS는 오름차순이니까)
            if(a[i] > a[j]){
                //i번째 원소를 포함한 부분 증가 수열이 더 크다면 dp를 갱신한다.
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
        //갱신된 dp가 현재 값보다 더 크다면 정답 변수 갱신
        ans = max(dp[i], ans);
    }
    cout << ans;
    
    return 0;
}