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

 

풀이 일시 : 2020-12-30

 

 

문제 : 

수열 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)

ex)

6

10 20 10 30 20 50

 

 

출력 : 

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

ex)

4

 

 

풀이 : 

부분수열을 구하는 것이다. 연속된다는 말이 없으니 총 부분수열의 갯수는 N^2일 것이다.

 

부분수열 중 증가하는 부분수열. 그 중 가장 긴 것을 찾으라고 한다. (합이 큰것X)

 

앞의 결과를 점차 뒤로 가면서 활용할 수 있으니 DP를 사용한다.

 

사실 코드도 몇 줄 안되는 이 문제를가지고 한참 고민했다.

 

아래는 이 문제를 풀이하며 적어둔 내 생각의 흐름이다. 결국 DP로 풀었지만 DP를 구성함에있어서도 많은 방법이 있기에 숙달되는 수 밖에 없다..

 

//생각의 흐름 1 : DP안쓰고 반복문으로만 -> 1 100 2 3 4 처리 X
//생각의 흐름 2 : DP순서를 앞에서 뒤로가면서 큰거나오면 처리
//생각의 흐름 3 : 뒤에서 앞으로 오면서 작은거나오면 처리
//생각의 흐름 4 : 앞에서 한칸씩 뒤로가면서 다시 앞을 훑으며 작은거찾아 DP채워나가기
//생각의 흐름 5 : 앞에서 한칸씩 뒤로가면서 다시 앞을 훑으며 큰거찾아 DP채워나가기

 

DP[i] 는 끝 지점의 인덱스가 i 일때 가장 긴 부분 수열을 저장하는 배열이다.

 

i=0일때는 (즉 인덱스가 0) 한가지 방법밖에 없을것으므로 1로 고정

 

i=1일때부터 N-1 번째까지 반복하며 DP[i]는 항상 자신을 포함해야하므로 최소값인 1로 두고 시작한다.

 

j=0부터 i-1 까지 반복하며 arr[i]>arr[j] && DP[i]<DP[j]+1 의 조건을 만족하면

( 앞의 값보다 현재의 값이 크고 && 앞에 것까지의 DP + 1 한것이 현재의 DP보다 크면 (즉 갱신될 조건이면) )

 

DP[i] = DP[j]+1을 수행해 DP[i]를 갱신해준다.

 

이와같이 수행하면서 max를 찾아 출력해준다.

 

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

const int MAX = 1001;
int arr[MAX];
int N;
int DP[MAX]; 
int result = 1;

int solution() {
	DP[0] = 1;
	for (int i = 1; i < N; i++) {
		DP[i] = 1;
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j] && DP[i] < DP[j] + 1) {
				DP[i] = DP[j] + 1;
			}
		}
		result = max(result, DP[i]);
	}
	return result;
}


int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	int result = solution();
	cout << result << '\n';
	return 0;
}

 

참고자료 :

dbstndi6316.tistory.com/35

[개념정리] DP 동적프로그래밍