[백준/BOJ][C++] 11053번 : 가장 긴 증가하는 부분 수열(DP)

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

문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

접근 방법

<처음 생각했던 접근 방법>

처음 이 문제를 보고 생각했던 풀이방식은 브루트포스 방식이었다. 이중 for문으로 각 i 마다 모든 j와 비교하여 i < j 일 때 카운트를 1씩 늘리고 i = j를 해주면서 구하는 방식을 떠올렸었는데, 이는 배열이 [10, 20, 90, 30, 40] 같은 경우에서 가장 긴 증가하는 부분 수열을 [10, 20, 90, 30, 40]로 판단하기 때문에 오답이다. (정답은 [10, 20, 90, 30, 40])

 

나는 10~20분 동안 접근 방법이 생각나지 않으면 DP 유형의 문제로 접근한다. (아직까지 DP 문제는 봐도 이게 DP 문제인지 잘 파악이 안 되기 때문이다.)

DP문제를 접근할 때는 i=1 일 때, i=2일 때 등 초반의 몇 개를 직접 구해보는 게 도움이 많이 된다.

1. i=1  / [10] 일 때

원소가 하나만 있으니 답은 1.

 

2. i=2 / [10, 20] 일 때

10 < 20이니 답은 2.

 

3. i=3 / [10, 20, 10] 일 때

idx [2]의 보다 작은 값이 앞에 없기 때문에 답은 자기 자신을 포함한 1.

#자신보다 작은 값이 앞에 있어야 한다는 발상을 떠올릴 수 있다.

 

4. i=4 / [10, 20, 10, 30] 일 때

이 내에서 나올 수 있는 증가하는 부분수열은 [10, 20, 10, 30], [10, 20, 10, 30], [10, 20, 10, 30], [10, 20, 10, 30],

[10, 20, 10, 30], [10, 20, 10, 30], [10, 20, 10, 30], [10, 20, 10, 30], [10, 20, 10, 30]가 있다.

#새로운 원소가 추가됐을 때, 앞에 있는 자신보다 작은 값이 가지는 가장 긴 수열의 뒤에 붙는다는 발상을 떠올릴 수 있다.

주의할 점

마지막 index가 포함된 가장 긴 부분수열을 구하는 것이 아닌, 존재할 수 있는 모든 부분수열 중 가장 긴 것을 고르는 문제이다.

코드

#include<iostream>
#include<algorithm>

using namespace std;

int arr[1001] = {0};  //입력받는 배열
int cnt[1001] = {0};  //arr[i]가 포함된 부분 수열 중 가장 긴 수열의 길이를 저장

void dp(int n){
	int big = 0;
	for(int i = 0; i < n; i++){
		if(arr[i] < arr[n] && cnt[i] > big)
			big = cnt[i];
	}
	cnt[n] = big + 1;	//자기자신을 포함할 때 +1
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	cnt[0] = 1;               //무조건 자기자신을 포함한 부분수열
	for(int i = 0; i < n; i++){
		cin >> arr[i];
	}
	int ans = 0;
	for(int i = 0; i < n; i++){
		dp(i);
		ans = max(cnt[i], ans); //주의할 점에 써놓은 부분
	}
	cout << ans;
}