[백준] 12015 - 가장 긴 증가하는 부분 수열2

12015. 가장 긴 증가하는 부분 수열 2 풀이

난이도: Gold II
문제 주소: https://www.acmicpc.net/problem/12015

문제 풀이

이 문제는 수열이 주어졌을 때, 가장 긴 증가하는 부분 수열(LIS)의 길이를 구해야 하는 문제이다.
처음에는 이전 LIS문제처럼 이중 반복문을 사용한 동적 계획법(DP) 을 생각했지만 배열의 크기가 최대 1,000,000까지 주어지기 때문에 일반적인 O(N^2) 방식으로 코드를 작성하면 안돼겠다 싶었다

대충 배열 크기상 이분탐색을 사용해야겠다고는 싶었는데 이분탐색을 어떻게 활용해야할지 처음에는 도저히 감이 잡히지 않았다

한시간쯤 고민이 넘어가닌까 이건 힌트가 필요하다 싶어서 ai를 이용해 힌트만을 받아봤다
그렇게 얻은 힌트는 최장 길이 수열의 원소는 찾을 필요없이 길이만 구할 생각을 하면 된다는 거였고 그렇게 다음과 같은 코드를 작성했다

for (int i = 0; i < n; i++) {
    if (lis.empty() || lis.back() < num[i]) {
        lis.push_back(num[i]);
    }
    else {
        auto it = lower_bound(lis.begin(), lis.end(), num[i]);
        *it = num[i];
    }
}

풀이의 핵심은 lis라는 벡터를 생성하여 수열의 요소를 처음부터 하나씩 확인해 나가는 것이다.

만약 벡터가 비어있거나 현재 확인 중인 숫자 num[i]가 lis 벡터의 가장 마지막 원소보다 크다면 오름차순 수열을 무사히 이어갈 수 있으므로 push_back을 통해 맨 뒤에 추가해 준다.

 

반대로 현재 숫자가 벡터의 마지막 원소보다 작거나 같다면 lower_bound 함수를 사용하여 벡터 내에서 현재 숫자보다 크거나 같은 첫 번째 위치를 찾은 뒤 그 값을 현재 숫자 num[i]로 덮어씌운다. 이렇게 하는 이유는 lis 벡터 내의 값들을 최대한 작게 유지해야 이후에 들어오는 값들을 수열에 추가할 수 있어지기 때문이다

 

결과적으로 모든 숫자에 대한 탐색이 끝난 후 lis.size()를 출력하면 가장 긴 증가하는 부분 수열의 길이가 바로 나오게 된다
이렇게 갱신된 벡터의 원소들이 실제 LIS를 이루는 원소들과 항상 일치하는 것은 아니지만 LIS의 길이 를 주어진 시간 안에 구할수 있어진다

최종 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <climits>
#include <unordered_set>

using namespace std;

int num[1000001];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> num[i];
    
    vector<int> lis;

    for (int i = 0; i < n; i++) {
        if (lis.empty() || lis.back() < num[i]) {
            lis.push_back(num[i]);
        }
        else {
            auto it = lower_bound(lis.begin(), lis.end(), num[i]);
            *it = num[i];
        }
    }
    cout << lis.size() << "\n";
    return 0;
    
}   

---

'Algorithm > 백준' 카테고리의 다른 글

[백준] 2239 - 스도쿠  (0)	2026.04.14
[백준] 5525 - IOIOI  (0)	2026.04.12
[백준] 11404 - 플로이드  (0)	2026.04.03
[백준] 9663 N－Queen  (0)	2026.04.01
[백준] 10814 - 나이순 정렬  (0)	2026.04.01