[백준] 11053번: 가장 긴 증가하는 부분 수열 (C++)

가장 긴 증가하는 부분 수열을 구하는 문제

문제 설명만 듣고는 도무지 이해가 되지 않았다

그냥 숫자가 커질 때 count하면 되지 않을까 라는 식으로

처음은 배열을 사용하지 않고 이전 값과의 비교 만으로 코드를 구성했다

int N;
    cin >> N;
    
    if(N == 1){
        return 0;
    }
    
    int ascent = 1;
    int input;
    int temp = 0;
    
    
    
    for(int i = 0; i < N; i++){
        cin >> input;
        if(i == 0){
            temp = input;
        }
        if(i > 0){
            if(temp < input){
                ascent++;
                temp = input;
            }
        }
        
        
    }
    
    cout << ascent;

그렇지만 반복된 '틀렸습니다'

예외사항이고 일단 문제가 이해가 가지 않았다

아무리 다른 반례를 찾아보아도 해결하지 못했다가 

아래의 반례를 보고 문제를 이해했다

그 전까지는 문제를 제대로 이해 못 한 셈이다

11
100 1 2 3 101 4 5 6 102 7 8
answer 8

이것이다

위 예제대로 하면 100부터 102까지가 카운트 되지만

문제에서 의도한 것은 무조건 큰 값이 아닌 

길이가 제일 큰 부분 배열을 구해야 하기 때문에

최대값을 가지는 것이 꼭 큰 부분 배열을 가지는 것이 아니다

 

결국 배열을 안 써서 해결하려고 했지만

배열을 쓸 수 밖에 없었다

 

우선 입력 값을 받는 배열을 저장한다

그 다음 dp 배열에서 인덱스마다 접근하여

역순으로 이전 값이 더 많이 연속적인지 비교한다

 

이후 count 변수에 최대 연속 값을 저장한 후 출력한다

// baekjoon 11053

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

// codes for fast I/O
void init(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
}

int MAX = 1001;

int main(){
    init();
    
    int N;
    cin >> N;
    
    int count = 0;
    int arr[MAX];
    int dp[MAX];
    
    
    for(int i = 1; i <= N; i++){
        cin >> arr[i];
    }
    
    for(int i = 1; i <= N; i++){
        dp[i] = 1;
        for(int j = i - 1; j >= 1; j--){
            if(arr[i] > arr[j]){
                dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        count = max(dp[i], count);
    }
    cout << count;
    
    return 0;
}

 

 

참고 사이트

글 읽기 - 반례 모음집 (acmicpc.net)

[ 백준 11053 ] 가장 긴 증가하는 부분 수열 (C++) :: 얍문's Coding World.. (tistory.com)