백준 11722 _ 가장 긴 감소하는 부분 수열

www.acmicpc.net/problem/11722

11722번: 가장 긴 감소하는 부분 수열

---

✨ 내 소스 코드

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int dp[1001];
	int seq[1001];
	int N,max_dp=0;
    
	cin >> N;
    
	for (int i = 0; i < N; i++) {
		cin >> seq[i];
		dp[i] = 1;
		for (int j = 0; j < i; j++) {
			if (seq[j] > seq[i]&& dp[j] + 1 > dp[i]&&max_dp<dp[j]) {
				max_dp = dp[j];	
			}
		}
		dp[i] += max_dp;
		max_dp = 0;
	}
	
	for (int i = 0; i < N; i++) {
		if (dp[i] > max_dp) {
			max_dp = dp[i];
		}
	}
    
	cout << max_dp;
	return 0;
}

 

🙏 문제 풀이

배열 dp[] 는 수열의 길이를 의미한다

dp[i] 는 seq[i]가 가질 수 있는 가장 긴 수열의 길이를 의미

 

 

→ 10이라는 값이 들어왔을 때, 그 이전 값이 없으므로 dp값을 1로 지정해준다

 

 

 

→ 30이라는 값이 들어왔을 때, 그 이전값들 중에 30보다 큰 값은 없으므로

수열의 길이는 1이 된다

 

 

→ 10이라는 값이 들어왔을 때, 이전 값들 중에 10보다 큰 30이라는 값이 존재한다

30의 수열의 길이 값을 더해주어, 수열의 길이가 2가 된다

 

 

 

→ 20이라는 값이 들어왔을 때, 이전 값들 중에 20보다 큰 값은 30밖에 존재하지 않는다

30의 수열의 길이 값을 더해주어, 수열의 길이가 2가 된다

 

 

→ 10이라는 값이 들어왔을 때, 이전 값들중에 10보다 큰 값은 30과 20 두 개가 존재한다

그러나 20의 수열의 길이(dp) 값이 30의 수열의 길이 값보다 크기때문에, 20의 수열의 길이 값을 더해주어 수열의 길이가 3이 된다

 

 

 

⭐ 문제 풀이 결과