문제
- 11053번 : 가장 긴 증가하는 부분 수열
- Rank : Silver II
- 링크 : https://www.acmicpc.net/problem/11053
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
풀이 전략
- for문을 사용하여, 현재 인덱스 앞에서 자기보다 큰, 방문할 수 있는 위치를 확인하여 진행한다.
- 20 20 50 10 70 -> 20에서 50을 방문할 경우, 70 방문하는 경우로 재귀 함수 호출
- 20 20 50 10 70 -> 70을 새로 방문 가능
- 20 20 50 10 70 -> 더 방문할 곳이 없으므로 종료됨
- 20 20 50 10 70 -> 20에서 50을 방문할 경우, 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!)가 되어 시간 초과로 실패하는 문제였다.
'Problem Solving > Backjoon' 카테고리의 다른 글
| [백준][C++]1043 - 거짓말 (0) | 2022.03.03 |
|---|---|
| [백준][C++]9663 - N-Queen (0) | 2022.03.02 |
| [백준][C++]10830 - 행렬 제곱 (0) | 2022.02.05 |
| [백준][C++]1007 - 벡터 매칭 (0) | 2022.01.25 |
| [백준][C++]17070 - 파이프 옮기기 1 (0) | 2022.01.22 |
