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

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

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

문제 풀이

가장 긴 증가하는 부분 수열(LIS})을 구하는 전형적인 DP문제다

수열의 크기 N이 최대 1,000이기 때문에 O(N^2) 으로 비교적 널널하게 해결 가능하다

풀이방식

1. 각 원소 그 자체만으로도 길이 1인 증가하는 부분 수열이 되므로 dp 배열의 모든 값을 1로 채운다
2. 이중 반복문으로 현재 위치 i를 기준으로 0부터 i-1까지의 이전 원소들을 j로 탐색한다
3. 만약 num[j] < num[i]라면 현재 원소가 이전 원소 뒤에 붙어 증가하는 수열을 만들 수 있다는 뜻이다. 이때 dp[i] = max(dp[i], dp[j] + 1)을 통해 최댓값을 갱신한다
4. 전체 dp 배열 중 가장 큰 값이 수열의 최대 길이라 마지막에 정렬을 이용해 최댓값을 찾았다

문제 자체는 정말 쉬운데 정렬을 안한상태로 dp[n - 1]을 출력했다가 한번 틀렸다....
이런거 실수하지 않도록 조심하자

최종 코드

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

using namespace std;

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

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

    fill(dp, dp + n, 1);

    for (int i = 1; i < n; i++) {
        for (int j = i - 1; j >= 0 ; j--) {
            if (num[j] < num[i])dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    sort(dp, dp + n);
    cout << dp[n - 1] ;
    return 0;
}

---

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

[백준] 12851 - 숨바꼭질2  (0)	2026.03.19
[백준] 12865 - 평범한 배낭  (0)	2026.03.17
[백준] 1654 - 랜선 자르기  (0)	2026.03.13
[백준] 10989 - 수 정렬하기 3  (0)	2026.03.08
백준 - 15829  (0)	2026.03.08