[C++]백준 - 11053번 문제

11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net)

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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

 

 

---

 

생각해 볼 점

---

문제의 조건에 맞게 코딩하면 됩니다.

 

수열이 있을 때 왼쪽의 수부터 다음과 같은 과정을 수행합니다.

 

예시 수열 : 1, 5, 3, 6, 20, 10, 20, 1

예시 길이 : 1, 2, 2, 3, 4,   4,  4,   1

 

 

1. 현재 자신의 위치보다 좌측에 자신보다 작은 수가 있는지 확인합니다.

2. 있다면, 해당 위치의 수열의 길이가 가장 큰 것을 택해서 1을 더하여 자신의 수열의 길이가 되도록 합니다.

3. 없다면, 자신의 수열의 길이를 1로 저장합니다.

 

수열의 길이를 동적계획법으로 저장하여 이용하면 됩니다.

 

코드

---

#include <iostream>
using namespace std;


int main()
{
    int N;
    cin >> N;
    
    int result = 0;
    
    int p[1001] = {0, };
    int dp[1001] = {0, };	//수열의 길이를 저장
    
    
    for(int i = 1; i < N+1; i++) 
    {
        cin >> p[i];
        int count = 0;
        
        //현재 값보다 작으며, 수열의 길이는 가장 큰 요소 탐색
        for(int j = i-1; 0 < j; j--)
        {
            if(p[j] < p[i] && count < dp[j]) 
            {
                count = dp[j];
            }
        }
        
        dp[i] = ++count;
        
        if(result < dp[i]) result = dp[i];
    }
    
    cout << result;
    return 0;
}

 

그 외

---

입력부에서 수행해도 무방한 알고리즘이므로 수행시간을 줄이기 위해 입력부에 코딩했는데, 다행히 잘 돌아가네요.