본문 바로가기
Algorithm 💫/Problem Solving

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

by 돼지고기맛있다 2021. 1. 8.
반응형

www.acmicpc.net/problem/11053

 

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

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

www.acmicpc.net

 

수열이 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 코드를 짜야한다!

 

10 20 10 30 20 50
1 2 1 3 2 4

 

방식은 우선 수열을 for문을 돈다. 그리고 맨 처음부터 해당 수까지 for문을 돌면서 자신보다 작은 아이가 있다면!

해당 dp의 수에 +1을 한 것과 현재 dp의 수를 비교하여 더 큰 값을 저장해준다. 그렇게 되면 앞에서 자기보다 작으면서 증가하는 부분 수열을 구할 수 있기 때문이다...

 

사실 이러한 방법은 처음 접해보는 방식이었기 때문에! ㅜㅠㅜㅠ 다른 포스팅들을 참고했다...! dp로 최소값과 최대값을 찾는게 왜인지 너무 어렵게 느껴진다... 반복학습 하다보면 익숙해질까아아~🙏

 

#include <iostream>
#include <vector>

using namespace std;

int arr[1001];
vector<int> dp(1001, 1);

int main()
{
    int n;
    cin >> n;

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

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j])
                dp[i] = max(dp[j] + 1, dp[i]);
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++)
        ans = max(ans, dp[i]);
        
    cout << ans << endl;
    return 0;
}
반응형

댓글