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

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

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

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

가장 긴 증가하는 부분 수열...

 

유명한 DP 문제인 건 알고 있었지만... 어렵지 않은 문제라고 생각했지만...

접근을 해봐도 틀렸다고 뜨고 이렇다할 풀이법이 나오지 않아서 결국 LIS 알고리즘을 봤던 문제

 

https://chanhuiseok.github.io/posts/algo-49/ 이 블로그가 도움이 되었다.

 

처음 했던 접근법은...

1. 입력을 받을 때마다 배열에 담는다.
2. 모든 배열의 요소를 현재 입력값보다 작은지 확인하고, 작다면 현재 입력값으로 갱신하고 해당 인덱스의 길이를 올려준다.
3. 가장 긴 길이를 출력한다.

 

설명으로 이해가 되지 않을 것 같아 코드를 첨부하자면..

#include<bits/stdc++.h>
using namespace std;

int main()
{
    vector<pair<int, int>> vec;
    int len, answer = 0;
    cin >> len;

    for (int i = 0; i < len; i++)
    {
        int input;
        cin >> input;

        for (int i = 0; i < vec.size(); i++)
        {
            // 현재까지 모든 요소와 비교하고 갱신
            if (input > vec[i].first)
            {
                vec[i].first = input;
                vec[i].second++;

                answer = max(vec[i].second, answer);
            }
        }

        vec.push_back({ input, 1 });
    }

    cout << answer;
}

언뜻 보면 맞는 것 같았지만, 맞을 리가 없었다. 가장 중요한 조건인 지울 수 있다는 조건을 이용하지 못한 코드라... 맞을 수가 없었다.

 

예를 들자면

input =>
1 2 10 3 4 5 6

이때 1과 2를 10으로 갱신해버려서 최대 길이가 31, 2, 10인 말도 안 되는 답이 나오는 것이다!

 

그래서 유명한 DP 알고리즘인 LIS 알고리즘을 배웠다.

#include<bits/stdc++.h>
using namespace std;


// first > value
// second > length
pair<int, int> arr[1000];

int main()
{
    int len, answer = 1, min = 1000;
    cin >> len;

    for (int i = 0; i < len; i++)
    {
        cin >> arr[i].first;
    }

    for (int i = 0; i < len; i++)
    {
        arr[i].second = 1;

        for (int j = 0; j < i; j++)
        {
            if (arr[j] < arr[i])
            {
                // 앞 값보다 크다면
                // 앞 길이와 비교해서 연장하거나 현재 값을 유지함
                arr[i].second = max(arr[i].second, arr[j].second + 1);
                answer = max(answer, arr[i].second);
            }
        }
    }

    cout << answer;

}

최댓값을 구하는 데 필요 없는 요소를 없는 취급하는 것에 최적화된 코드였다!

전 값보다 크다면 그 길이에 1을 늘리거나, 현재 길이를 유지한다니!! 간단하지만, 문제에 꼭 맞는 코드였다.

 

생각보다 간단한 코드라 조금만 더 고민했으면 나왔을 것도 같아서 아쉽다...

 

삽질하는 시간을 줄여서 효율적인 알고리즘을 공부하는 것도 중요하지만, 알고리즘에 이렇게 많은 시간을 쏟을 수 있는 때는 지금뿐이라는 걸 명심하고 앞으로는 삽질도 더 하고 고민도 하면서 문제를 풀어나가야겠다.

 

물론 삽질은 안 하는 편이 가장 좋지만 말이다...

파이팅 이민영!!!!