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

1. 문제 링크

 

www.acmicpc.net/problem/11053

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

 

 

2. 문제 설명

수열을 입력받은 후, 가장 긴 증가하는 부분 수열의 길이를 출력하는 문제입니다.

다이나믹 프로그래밍으로 풀 수 있는 문제입니다.

 

 

 

3. 소스코드

BOJ 11053번 가장 긴 증가하는 부분 수열 C++ 풀이입니다.

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

int d[1000];
int a[1000];

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> a[i];

	d[0] = 1;
	for (int i = 1; i < N; i++) {
		d[i] = 1;
		for (int j = 0; j < i; j++) {
			if (a[j] < a[i])
				d[i] = max(d[i], d[j] + 1);
		}
	}
	cout << *max_element(d, d + N);

	return 0;
}

5번 라인 :  다이나믹 프로그래밍으로 문제를 풀기 위해 길이가 수열의 크기의 최댓값(1000)인 배열을 선언했습니다. d[i]에는 i번째 수열의 항을 마지막으로 포함하는 부분 수열의 길이의 최댓값을 저장합니다.

6번 라인 : 수열의 각 항의 값을 입력받기 길이가 1000인 배열을 선언했습니다.

16번 라인 : 수열의 각 항의 값을 입력받아 배열 a에 저장합니다.

18번 라인 : d[0]은 0번째 항을 마지막으로 포함하는 부분 수열의 길이의 최댓값이므로 {a[0]}을 의미합니다. 따라서 1을 저장합니다.

19번 라인 : i = 1부터 N - 1까지 for문을 돌 때

20번 라인 : d[i]의 최솟값은 {a[i]}로 길이가 1이므로 일단 1로 초기화합니다.

21번 라인 : d[i]는 i번째 항을 마지막으로 포함하는 부분 수열의 길이의 최댓값이므로 for문을 이용해 j = 0부터 j < i까지 돌면서,

22번 라인 : j번째 수열의 항이 i번째 수열의 항보다 작다면 (예를 들어, a = {10, 30, 20}이고 i = 2라면 j = 0일 때는 10(a[j]) < 20(a[i])이므로 증가하는 부분 수열이 성립하지만, j = 1일 때는 30(a[j]) < 20(a[i])가 성립하지 않으므로 증가하는 부분 수열이 될 수 없습니다.)

23번 라인 : d[i]는 현재까지 i번째 항을 마지막으로 포함하는 부분 수열의 길이의 최댓값(d[i])과, j번째 항을 마지막으로 포함하는 부분 수열의 길이의 최댓값(d[j])에 i번째 항을 추가한 값인 d[j] + 1 중에서 큰 값을 d[i]에 저장합니다.

26번 라인 : d[0] ~ d[N - 1]까지의 값 중에서 최댓값을 출력하면 되고, 이를 구하기 위해 max_element함수를 사용했습니다.