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

문제

• 11053번 : 가장 긴 증가하는 부분 수열
• Rank : Silver II
• 링크 : https://www.acmicpc.net/problem/11053

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

풀이 전략

• for문을 사용하여, 현재 인덱스 앞에서 자기보다 큰, 방문할 수 있는 위치를 확인하여 진행한다.
  • 20 20 50 10 70 -> 20에서 50을 방문할 경우, 70 방문하는 경우로 재귀 함수 호출
    • 20 20 50 10 70 -> 70을 새로 방문 가능
    • 20 20 50 10 70 -> 더 방문할 곳이 없으므로 종료됨
• 해당 index를 방문할 때의 길이를 기록하여, 더 작은 부분수열로 방문하지 않도록 한다
  • A : 10 20 30 50 70  / i=4의 Length = 5 기록
  • B : 10 20 30 50 70  / i=4의 Length = 3 : 기록된 Length = 5보다 작으므로 방문하지 않음
• 일 때, 방문시 최대 길이를 기록해 둘 경우 Length = 5 에서만 방문하면 된다.
• 재귀함수로 구현하고, for loop를 사용한 호출이 끝난 후 최대 길이를 확인하여 기록한다.

void run(int idx, int current, int length)
{
	for (int i = idx; i < N; i++)
	{
		if (current < A[i] && visitLength[i] < length+1)
		{
			visitLength[i] = length + 1;
			run(i, A[i], length + 1);
		}
	}
	if (maxLength < length)
	{
		maxLength = length;
	}

}

전체 소스 코드

//Backjoon Problem No.11053
//https://www.acmicpc.net/problem/11053
//Mist16, 2022-03-01

#include <iostream>

using namespace std;

int A[1000]= { 0, };
int visitLength[1000] = { 0, };
int N = 0;

int maxLength = 0;

void run(int idx, int current, int length)
{
	for (int i = idx; i < N; i++)
	{
		if (current < A[i] && visitLength[i] < length+1)
		{
			visitLength[i] = length + 1;
			run(i, A[i], length + 1);
		}
	}
	if (maxLength < length)
	{
		maxLength = length;
	}

}

int main()
{
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}
	run(0, 0, 0);
	cout << maxLength;

	return 0;
}

Note

• 조건을 검사하지 않고, 방문하지 않을 경우에도 재귀함수를 호출할 경우에는 O(n!)가 되어 시간 초과로 실패하는 문제였다.