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

Silver II 난이도 문제를 C++로 풀이한 내용입니다. 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 구하는 동적 계획법 문제입니다.

문제 소개

문제 번호: 11053
문제명: 가장 긴 증가하는 부분 수열
난이도: Silver_II
사용 언어: C++
실행 시간: 0 ms
메모리: 2024 KB

이 문제는 길이가 N인 수열이 주어질 때, 수열에서 증가하는 부분 수열 중 가장 긴 것의 길이를 구하는 문제입니다. 부분 수열은 원래 수열에서 연속되지 않아도 되며, 오름차순으로 증가해야 합니다[1].

접근 방법

수열에서 **LIS(Longest Increasing Subsequence)**를 구하는 전형적인 DP 문제입니다.

• 핵심 아이디어: dp[i]를 **"i번째 원소를 마지막으로 사용하는 LIS의 길이"**로 정의
• 왜 이 방법? 각 위치에서 이전 모든 위치를 확인하여 최대 길이를 갱신하는 방식이 직관적이고 정확함
• 사용 자료구조: 1차원 DP 배열 + 벡터로 입력 저장

O(N²) 시간복잡도가 허용되는 N≤1000 크기에 적합합니다[1].

풀이 과정

1. 입력 처리: N개의 수열을 1-index로 벡터에 저장
2. DP 초기화: 모든 dp[i] = 1 (자기 자신만으로 구성된 수열 길이)
3. DP 채우기:
   • 각 i에 대해 1부터 i-1까지 j 탐색
   • v[i] > v[j]이면 dp[i] = max(dp[i], dp[j] + 1)
4. 답 도출: 모든 dp[i] 중 최대값

주의할 점:

• LIS는 반드시 마지막 원소에서 끝나지 않음 → 전체 dp 최대값 확인 필요
• 1-index 사용으로 인덱스 에러 방지 및 수식 단순화[1]

코드 설명

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

int dp[1001]; 
// dp[i] = "i번째 원소를 마지막으로 사용하는 LIS 길이"
// i번째 원소 이전의 원소들은 최대 수열 길이를 위해 교체될 수 있음
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> v(n+1);
    // 1-index 사용: 수식(dp, j < i) 그대로 쓰기 편하게
    // 수열 입력
    for(int i = 1; i <= n; i++){
        cin >> v[i];

    }

    // LIS DP 시작
    for(int i = 1; i <= n; i++){ // i가 n까지 간다
        dp[i] = 1;
        // 자기 자신 하나만 쓰는 증가 수열은 항상 가능
        // 모든 LIS의 최소 길이는 1

        for(int j = 1; j < i; j++){
            // i보다 앞에 있는 모든 원소 탐색
            // 바로 직전(i-1)만 보는 게 아니라 매 i 마다 '전체 과거 j들'을 봄

            if(v[i] - v[j]> 0){ // i보다 앞의 원소가 i보다 작으면 즉, 증가하면
                // dp[i] = "i번째 원소를 마지막으로 사용하는 LIS 길이"
                dp[i] = max(dp[i], dp[j] + 1);
                // j에서 끝나는 LIS 뒤에 i를 붙여보고 
                // 현재까지 알려진 최대 길이인 dp[i]보다 크면 그 값을 채택한다. 
                // 이를 반복하여 여러 j (1 ~ i-1) 중에서 가장 큰 dp[j] + 1 값 선택
                // 증가하는 경우가 하나도 없으면 dp[i]로 유지.
            }
        }
    }

    int ans = 0;
    for(int i = 1; i <= n; i++){
        ans = max(ans, dp[i]);
        // LIS는 반드시 n에서 끝난다는 보장이 없음
        // 모든 dp[i] 중 최대값이 진짜 LIS
    }

    cout << ans;
}

주요 코드 포인트:

• 상세한 주석으로 DP 의미와 갱신 로직 명확히 설명
• ios::sync_with_stdio(false); cin.tie(NULL);로 입출력 최적화
• v[i] - v[j] > 0 조건으로 증가 확인 (음수 처리 안전)

복잡도 분석

• 시간 복잡도: O(N²)
  중첩 for문으로 각 i마다 1~i-1까지 확인[1]
• 공간 복잡도: O(N)
  dp 배열과 벡터 각각 O(N)

N=1000일 때 10⁶ 연산으로 충분히 통과[1].

배운 점

• DP 상태 정의의 중요성: dp[i] = i번째 원소로 끝나는 LIS 길이라는 명확한 정의가 풀이의 핵심
• 1-index 활용: 인덱스 관리를 단순화하고 수식 유지에 유리
• 최적화 습관: C++에서는 입출력 최적화 필수
• LIS 기본: O(N log N) 이진탐색 버전 배워 확장 가능[1]

이 접근법은 다른 LIS 변형 문제(가장 긴 감소 부분수열 등)에도 그대로 적용 가능합니다.