백준 14002번 가장 긴 증가하는 부분 수열 4

 

 

 

문제 보러가기 : https://www.acmicpc.net/problem/14002

 

 

 

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

 

 

이번 문제는 다이나믹 프로그래밍 문제였습니다.

 

11053번 가장 긴 증가하는 부분 수열 문제에서 조금 더 확장된 문제입니다.

 

가장 긴 증가하는 부분 수열의 길이 뿐만 아니라 가장 긴 증가하는 부분 수열도 출력해야 하기 때문에 부분 수열을 갱신할 벡터와 가장 긴 증가하는 부분 수열을 담을 벡터, 2개가 필요합니다.

 

 

 

《문제 풀이》

 

1. 자신의 증가하는 부분 수열의 길이는 1이므로 cnt 배열을 1로 초기화 

2. 이중 포문을 통해 부분 수열 갱신

     (1) 현재 값이 비교 값보다 크고 갱신이 가능한 상태라면

         (1) update 배열을 클리어한 후 자신을 제외한 부분 수열 삽입 (오름차순을 위해 자신은 마지막에 삽입)

         (2) 부분 수열 갱신 가능 여부를 따지기 위해 cnt 배열 갱신

     (2) 현재 인덱스의 update 벡터 크기가 result 벡터 크기보다 크다면 result = update[i]

3. 가장 긴 증가하는 부분 수열의 길이는 result 벡터의 크기

4. 가장 긴 증가하는 부분 수열은 result 벡터의 원소들 

 

 

 

《C++ 코드》

 

#include <bits/stdc++.h>
#define MAX 1000

using namespace std;

int arr[MAX];
int cnt[MAX];
vector<int> update[MAX]; // 부분 수열 갱신을 위한 벡터  
vector<int> result;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int N;
	cin>>N;
	
	for(int i=0; i<N; i++) 
		cin>>arr[i];
	
	// 자신의 증가하는 부분 수열의 길이는 1  
	fill_n(cnt, N, 1);
		
	for(int i=0; i<N; i++) {
		int curVal = arr[i];
		update[i].push_back(curVal);  
		
		for(int j=0; j<i; j++) {
			
			// 현재 값이 더 크고 갱신이 가능하다면  
			if(arr[j] < curVal && cnt[i] < cnt[j] + 1) {
				update[i].clear();
				update[i] = update[j]; // 자신을 제외한 부분 수열 삽입  
				update[i].push_back(curVal); // 자신 삽입  
				cnt[i] = cnt[j] + 1;
			}
		}
		// 부분 수열 갱신하기  
		if(result.size() < update[i].size())
			result = update[i];
	}
	
	int size = result.size();
	cout<<size<<"\n"; // 가장 긴 증가하는 부분 수열의 길이  
	for(int i=0; i<size; i++)
		cout<<result[i]<<" "; // 가장 긴 증가하는 부분 수열
		
	return 0;
}

 

 

개발 환경: Dev-C++

 

 

 

baekjoon - 정답 화면