[백준] 11053번 C/C++ 풀이 _ 가장 긴 증가하는 수열

 

- 출처 : https://www.acmicpc.net/problem/11053 

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초256 MB196587169493937.662%

문제

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

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {1020, 10, 30, 20, 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

출처

알고리즘 분류











 


- 풀이 : 

풀이가 처음에 떠오르지 않아서 결국 다른 분의 도움을 받게 되었습니다. 




위와 같은 수열이 있다고 가정해보겠습니다. 
위의 수열에서 가장 긴 증가하는 수열은 아래와 같습니다. 



풀이 방법은 아래의 과정을 따라가면 됩니다.
먼저, 최장 증가 수열에 대한 길이를 알기 위한 배열이 하나 필요합니다. 

해당 배열에는 특징이 있습니다. 

- 값이 있는 부분의 뒤에서 부터 탐색합니다.
- 탐색 인덱스의 값보다 새로 들어올 값이 클 경우에는, 탐색 인덱스 다음 자리에 넣어줍니다.
- 탐색 인덱스가 맨 처음 인덱스까지 가도 자신보다 작은 인덱스를 못 찾으면, 맨 처음에 넣어 줍니다. 
- 항상 배열에 들어간 숫자의 개수가 최장 수열의 길이입니다. 

아래는 위의 예시를 수행하는 과정을 그림으로 표시해 본 것입니다. 







- 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
///////////////////////////////////
////////// 전역 변수 ///////////////
///////////////////////////////////
int N; 
vector<int> answer_vec;
 
///////////////////////////////////
////////// 메인 함수 ///////////////
///////////////////////////////////
int main() {
    cin >> N;
 
    // 초기값 받기 
    int sub; 
    cin >> sub; 
    answer_vec.push_back(sub);
 
    // 벡터에 값 대입받기 
    for (int n_idx = 1; n_idx < N; n_idx++) {
        int sub; 
        cin >> sub; 
 
        // 크기 확인.    뒤에서 부터 접근하면서 크기를 확인한다. 
        int ans_vec_size = answer_vec.size();
        for (int conf_idx = ans_vec_size-1; conf_idx >=0 ; conf_idx--) {
            // sub 가 더 크면 현재 인덱스의 다음 인덱스에 밀어 넣는다. 
            if (answer_vec.at(conf_idx) < sub ) {
                // 만약 마지막 인덱스보다 값이 크면 push 를 사용하여 추가하고, 
                // 아니면 값을 교체한다.  
                if (conf_idx == ans_vec_size - 1) answer_vec.push_back(sub);
                else answer_vec.at(conf_idx+ 1 ) = sub;
                break;
            } 
            // 맨 첫 번째 인덱스 까지 갔는데 교체가 없으면, 0번 인덱스와 교환
            if ( conf_idx == 0 ) answer_vec.at(0= sub;
        }
 
    }
 
    cout << answer_vec.size();
 
    return 0;
}
cs