알고리즘 - 백준 11053 (가장 긴 증가하는 부분 수열)

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

11053번: 가장 긴 증가하는 부분 수열

 

---

 

문제

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

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

 

입력

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

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

 

출력

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

 

---

 

풀이 및 코드

입력 수열에서 가장 긴 증가하는 부분 수열을 구할 수 있는 방법을 표로 나타내면 다음과 같다.

[0]	[1]	[2]	[3]	[4]	[5]
10	20	10	30	20	50
1	2 (10, 20)	1	3 (10, 20, 30)	2 (10, 20)	4 (10, 20, 30, 50)

위 표를 풀어서 쓰면 다음과 같이 쓸 수 있다.

[0]이 포함되는 부분 수열 중 가장 긴 증가하는 부분 수열은 {10}으로 원소의 개수는 1개이다.

[1]이 포함되는 부분 수열 중 가장 긴 증가하는 부분 수열은 {10, 20}으로 원소의 개수는 2개이다.

[2]이 포함되는 부분 수열 중 가장 긴 증가하는 부분 수열은 {10}으로 원소의 개수는 1개이다.

이런 식으로 마지막 [5]이 포함되는 부분 수열 중 가장 긴 증가하는 부분 수열은 {10, 20, 30, 50}으로 원소의 개수는 4개이다.

결국,

1) 각 [i] 번째의 원소의 개수를 구하기 위해서는 [0] ~ [i - 1]까지의 원소들 중 [i] 번째의 원소보다 작은 것들을 뽑고,

2) 작은 것들 중 가장 큰 원소의 개수에 1을 더한 것과 같다.

위에 말로 풀어 쓴 식을 코드로 표현하면 다음과 같다.

#include <iostream>
using namespace std;

int input[1000];
int dp[1000];
int main(){
    int n;
    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> input[i];
    }

    dp[0] = 1;
    int result = 1;
    for(int i = 1; i < n; i++){
        int temp = 0;
        dp[i] = 1;
        for(int j = 0; j < i; j++){
            if(input[i] > input[j]){
                if(temp < dp[j]){
                    temp = dp[j];
                    dp[i] = temp + 1;
                }
            }
        }
        if(result < dp[i])
            result = dp[i];
    }

    cout << result << endl;

    return 0;
}

 

https://github.com/haram1117/AlgorithmStudy/commit/d7649d19c48b70fb9a8ff6bc1fd679dbb6fa2196

DP11053 · haram1117/AlgorithmStudy@d7649d1