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

BOJ 바로가기

#include <iostream>
using namespace std;
int go(int);
int d[1001] = { 0 };
int arr[1001] = { 0 };
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n; cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	int max = 1; // 길이는 1 이상
	for (int i = 1; i <= n; i++) {
		if (i == 1)
			max = go(i);
		else
			if (go(i) > max)
				max = go(i);
	}
	cout << max;
	return 0;
}
int go(int n) {
	d[1] = 1;
	if (d[n])
		return d[n];
	for (int i = 1; i < n; i++) {
		if (arr[i] < arr[n])
			d[n] = max(d[n], d[i] + 1);
	}
	if (d[n] == 0) // arr[n]이 배열에서 가장 작은 수일 경우
		d[n] = 1;
	return d[n];
}

문제를 잘못 이해해서 한참 잘못 풀었다가 나중에야 정확히 이해했다.
수열 A = {10, 20, 10, 30, 20, 50}가 있을 때 가장 긴 증가하는 수열은 {10, 20, 30, 50}이다. 수열 A에서 만들 수 있는 증가하는 수열은 {10, 20}, {10, 20, 50} 등이 있는데, 이 중에서 '가장 긴' 수열을 찾아낸 다음 그 길이를 구해야 한다.

나는 이 문제를 TOP-DOWN 방식으로 해결했다.
d[n]은 길이가 n개인 수열에서 가장 긴 증가하는 수열의 길이를 의미한다.

int go(int n) {
	d[1] = 1;
	if (d[n])
		return d[n];
	for (int i = 1; i < n; i++) {
		if (arr[i] < arr[n])
			d[n] = max(d[n], d[i] + 1);
	}
	if (d[n] == 0) // arr[n]이 배열에서 가장 작은 수일 경우
		d[n] = 1;
	return d[n];
}

0으로 초기화된 배열 d가 있다. arr[n]보다 작으면서 가장 큰 arr[i]를 구한 다음 d[n]에 d[i]+1의 값을 넣어주었다.

이때 주의해야 할 것이 있다. arr[n]보다 작으면서 가장 큰 arr[i]가 없을 경우, 즉 arr[n]이 가장 작은 숫자일 경우에 d[n]은 1이 되어야 한다. 나는 이 부분을 놓쳐서 자꾸 틀리는 바람에 한참을 헤맸다. 다음의 코드를 빼먹지 않도록 주의해야한다.

if (d[n] == 0) // arr[n]이 배열에서 가장 작은 수일 경우
		d[n] = 1;

main함수에서는 go(1), go(2), ... , go(n)의 값 중 가장 큰 값을 변수 max에 할당한 다음 출력해주었다.