[DP] 백준 문제 풀이 - 11053 가장 긴 증가하는 부분 수열

👩🏻‍💻 문제링크

https://www.acmicpc.net/problem/11053

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

 

✍️ 아이디어 (처음에 아이디어 자체가 생각 안나서 강의 봄)

1. 문제 이해

• 부분 수열중에서 증가하고 가장 긴것을 찾는 문제

2. 이 문제의 특이한 점은 지금 까지 문제는 맨 마지막에 D[N]이 문제의 답이 되었다면 이 문제는 마지막 D[N]이 답이 아니라 점화식에서 가장 max 값이 답이라는 것이다

3. 점화식 D[N] = 수열의 길이가 N일때 가장 긴 증가하는 수열의 길이

ex)  arr    : 10, 20, 10, 30,  20,  50

       result : 1, 1+1, 1, 2+1,1+1,3+1

->  자신보다 작은 숫자의 위치를 기준으로 해당 dp중 가장 큰 값으로 갱신

✍️소스코드

#include <iostream>
#include <algorithm>
using namespace std;

int result[1001];

int main()
{
	int n; cin>>n;
	int arr[n+1]={0};
	for(int i=1; i<=n; i++)
	{
		cin>>arr[i];
	}
	result[1]=1;
	for(int i=2; i<=n; i++)
	{
		result[i]=1;
		int max=0;
		for(int j=1; j<i; j++)
		{
			if(arr[i]<=arr[j]) // 앞의 수가 지금 수보다 크거나 같으면 건너 뛰어
			{
				continue;
			}
			if(max<result[j]) // 앞의 수가 지금 수보다 작은경우 실행
			{
				max=result[j]; // 앞의 수가 지금 수보다 작은데 max인 경우 갱신
			}
		}
		result[i]+=max;
	}
	cout<<*max_element(result, result+n+1)<<'\n';
}

 

• 다른 사람의 코드 (한번에 배열을 받지 않고 한개씩 함)

#include <iostream>
#include <vector>
#include <algorithm>

#pragma warning(disable: 4996)

using namespace std;

int main() {
    int T;
    int N, M, K, H;
    int X, Y;
    int answer = 0;
    
    int dp[1001];
    vector<int> v;
    cin >> T;

    for (int i = 0; i < T; i++) {
        cin >> K;
        v.emplace_back(K);
        int dp_max = 0;

        for (int j = 0; j < v.size(); j++) {
            if (v[i] > v[j]) {
                if (dp_max < dp[j])
                    dp_max = dp[j];
            }
        }
        dp[i] = dp_max + 1;
        answer = max(answer, dp[i]);
    }

    cout << answer << endl;

    return 0;
}

 

체감난이도	걸린시간	참고	사용 문법
상	25min	강의 아이디어 참고함(코드는 안봄)	DP인데 맨 마지막 점화식 D[N]이 정답이 아닐수도 있는 DP