PS/BaekJoon

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

박땅콩 2022. 8. 17.

728x90

※주의※
저의 풀이가 정답은 아닙니다.
다른 코드가 더 효율적이거나 좋을 수 있습니다.
언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

[문제 풀이 사이트]

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

[문제 설명]

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

[입력]

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

[출력]

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

[입출력 예]

입력	출력
6 10 20 10 30 20 50	4

[문제 풀이]

이 문제는 아래 포스트 방법 1의 내용으로 코드를 작성하였다.

[Algorithm] 최장 증가 부분 수열(LIS)

DP 문제인 LIS 문제를 풀기 위해 LIS 알고리즘을 공부했습니다. 제가 공부한 내용을 바탕으로 작성해보려고 합니다. 잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적부탁드립니다. 최

park-peanut.tistory.com

그리고 비슷한 문제로 1965번 상자 넣기 문제도 있어서 함께 풀어보면 좋을 것 같다.

1965번: 상자넣기

정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가

www.acmicpc.net

[최종 코드]

[GitHub]

GitHub - SmallPanutPark/BAEKJOON: Study BaekJoon for Coding Test

Study BaekJoon for Coding Test. Contribute to SmallPeanutPark/BAEKJOON development by creating an account on GitHub.

github.com

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

int N; // 수열의 크기

int lengthOfLIS(vector<int>& A) {
    vector<int> dp(N, 1);
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < i; ++j) {
            if(A[i] > A[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    return *max_element(dp.begin(), dp.end()); // 원소 중 최댓값을 리턴
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    vector<int> A;
    for(int i = 0; i < N; ++i) {
        int n; cin >> n; // 수열 입력
        A.emplace_back(n);
    }
    cout << lengthOfLIS(A);
}