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

 

 

 

 

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

 

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

 

 

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

 

 

 

 

《문제 풀이》

 

1. 크기가 N인 arr 배열의 원소 입력 

2. 가장 긴 증가하는 부분 수열의 길이를 구하기 위한 새로운 cnt 배열 생성

3. cnt 배열을 모두 1로 초기화 (자기 자신의 가장 긴 증가하는 부분 수열의 길이는 항상 1임)

4. arr 배열의 i번째 원소와(0 < i < N) j번째 원소(0 <= j < i) 각각을 비교하며 자기 자신이 더 크면 

    cnt[i] = max(cnt[i], cnt[j] + 1) 을 수행하여 cnt[i] 값 갱신 

5. i++ 될 때마다 result = max(result, cnt[i])을 수행하여 결과값 갱신 

 

 

 

《C++ 코드》

 

#include <iostream>
#include <cstring>
#define MAX 1000

using namespace std;

int arr[MAX];  
int cnt[MAX]; 

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로 초기화  
	//자기 자신의 증가하는 부분 수열의 길이는 1 
	fill_n(cnt, N, 1);
	
	int result = 1;
	for(int i=1; i<N; i++){
		int curVal = arr[i];
		
		for(int j=0; j<i; j++){
			if(arr[j] < curVal) //자기 자신이 더 크면  
				cnt[i] = max(cnt[i], cnt[j] + 1);
		}
		result = max(result, cnt[i]); //결과값 갱신  
	}
	
	cout<<result<<"/n";
	return 0;
}

 

개발 환경 : Dev-C++

 

 

 

Baekjoon - 정답 화면