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

 

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

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

[문제 풀이]

다이나믹 프로그래밍을 이용하여 문제를 풀었습니다.

 

이 문제는 증가하는 부분 수열 중에 가장 긴 부분 수열을 찾는 문제입니다. 부분 수열을 찾기 위해 DP 배열을 선언하여 메모제이션 해주었습니다. 2중 반복문을 돌면서 0번째 인덱스부터 i번째 인덱스까지 반복하면서 자신보다 값이 작은 경우가 있다면

dp[i] = max(dp[i], dp[j] + 1) 

을 이용하여 메모제이션 해주었습니다. 

[코드]

#include<iostream>
#include<algorithm>

using namespace std;

int N;
int result = 0;

int A[1001];
int dp[1001];

int main() {

	scanf("%d", &N);

	for (int i = 0; i < N; i++)
		scanf("%d", &A[i]);


	for (int i = 0; i < N; i++) {

		dp[i] = 1;

		for (int j = 0; j < i; j++) {

			if (A[i] > A[j]) {

				dp[i] = max(dp[i], dp[j] + 1);
			}
		}

		result = max(result, dp[i]);
	}

	printf("%d\n", result);
	return 0;
}