백준 11053 가장 긴 증가하는 부분 수열 C++

문제

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

 

내 풀이

예시

d 0 1 2 3 4 5

10 20 10 30 20 50

1 1 1 1 1 1

i = 0 인 경우

i = 1 인 경우

a[1] > a[0]

d[0] = 1

d[1] = max ( d[1] , d[0] + 1) = max (1, 2) = 2

i = 2 인 경우

a[2] > a[0] 가 아니고

a[2] > a[1] 가 아니므로

d[2]는 초기값 1 그대로 유지

d[2] = 1

i = 3인 경우

a[3] > a[0] 이므로

d[3] = max (d[3], d[0] + 1) = max(1, 1 + 1) = 2

a[3] > a[1] 이므로

d[3] = max (d[3], d[1] + 1) = max(2, 2 + 1) = 3

a[3] > a[2] 이므로

d[3] = max (d[3], d[2] + 1) = max(3, 1 + 1) = 2

따라서 d[3] = 3

…

증가하는 수열이 나오면 +1 갱신!!

다이나믹 프로그래밍 활용

 

#include <iostream>

#define MAX 1001
using namespace std;

int n, result = 0;
int a[MAX];
int d[MAX];

int max(int x, int y) { 
	if (x > y) {
		return x;
	}
	return y;
}


int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	
	
	for (int i = 1; i <= n; i++) {
		d[i] = 1;
		for (int j = 1; j < i; j++) {
			if (a[i] > a[j]) {
				d[i] = max(d[i], d[j] + 1);
			}
		}
		result = max(d[i], result);
	}
	cout << result;
	return 0;
}