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

BOJ 바로가기

▼ 내 소스코드

#include <iostream>
using namespace std;
int go(int);
int d[1001] = { 0 }, dnum[1001][1001] = { 0 }, 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 이상
	int p = 0;
	for (int i = 1; i <= n; i++) {
		if (i == 1) {
			max = go(i);
			p = i;
		}
		else
			if (go(i) > max) {
				max = go(i);
				p = i;
			}
	}
	cout << max <<'\n';
	for (int i = 1; dnum[p][i] != 0; i++) {
		cout << dnum[p][i] << ' ';
	}
	return 0;
}
int go(int n) {
	d[1] = 1; dnum[1][1] = arr[1];
	if (d[n])
		return d[n];
	int k;
	// d[n]을 가능한 한 최댓값으로 갱신
	for (int i = 1; i < n; i++) {
		if (arr[i] < arr[n]) {
			if (d[n] < d[i] + 1) {
				d[n] = max(d[n], d[i] + 1);
				k = i;
			}
		}
	}
	// dnum 배열에 값 넣어주기
	if (d[n] != 0) {
		for (int i = 1; i <= n-1; i++) {
			dnum[n][i] = dnum[k][i]; // 새로운 배열에 가장 긴 배열 복붙
		}
		for (int i = 1; i <= n ; i++) { // 배열의 마지막에 arr[n] 추가
			if (dnum[n][i] == 0) {
				dnum[n][i] = arr[n];
				break;
			}
		}
	}
	else { // arr[n]이 배열에서 가장 작은 수일 경우
		d[n] = 1;
		dnum[n][1] = arr[n];
	}
	return d[n];
}

[백준11053] 가장 긴 증가하는 부분 수열 (C++)
위 문제와 거의 비슷한 문제다. 다른 점이 있다면 수열의 모든 수를 출력해야 한다는 것. 어떻게 구현할지 고민하다가 이차원 배열을 만들어서 d[n]에 대응하는 수열을 저장해주는 방식으로 문제를 풀었다. 이후 백준님의 알고리즘 강의를 들어보니 '역추적' 방식을 통해 보다 쉽게 구현할 수 있었다.

▼ 참고 소스코드

void go(int p) {
    // ? -> ? -> ... a[v[p]] -> a[p]
    // ---------------------
    //        go(v[p]);
    if (p == -1) {
        return ;
    }
    go(v[p]);
    cout << a[p] << ' ';
}

v[p]는 a[p]로 가기 위한 연결장치 역할을 한다. 함수 안에서 다시 함수를 호출하는 방식을 통해 수열 안의 수가 차례대로 출력된다. 이 알고리즘을 기억해 두는 게 좋겠다.