[백준][dp] 11053 가장 긴 증가하는 부분 수열 c++ 구현

목차

https://www.acmicpc.net/problem/11053

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

 

문제

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 구현 방향

다이나믹 프로그래밍의 방법 중 하나인 상향식을 이용해 구현하고자 했다.

다이나믹 프로그래밍의 개념을 모른다면 아래 링크를 참고하면 좋다

https://be-senior-developer.tistory.com/19

[DP] 동적 계획법 알고리즘 c++ 설명

 

 

 

문제 풀이

각 수까지 만들어지는 수열의 개수를 세주고 그것을 점화식으로 만들면 된다.

(형광색 표시한 것: 현재 값보다 작은 수 중 수열의 개수가 가장 큰 수)

예시)  35 100 20 30 25 40

 

• 35보다 작은 수가 없으므로 자기 자신만 세어준다.

1

 

 

• 100보다 작은 수 중 수열의 개수가 가장 큰 것은 35이므로 수열의 개수는 1+1 이다.

1

2

 

 

• 20보다 작은 수가 없으므로 자기 자신만 세어준다.

1

2

1

 

 

• 30보다 작은 수 중 수열의 개수가 가장 큰 것은 20이므로 수열의 개수는 1+1 이다.

1

2

1

2

 

 

• 25보다 작은 수 중 수열의 개수가 가장 큰 것은 20이므로 수열의 개수는 1+1 이다.

1

2

1

2

2

 

 

• 40보다 작은 수 중 수열의 개수가 가장 큰 것은 30이므로 수열의 개수는 2+1 이다.

1

2

1

2

2

3

 

 

이 중 수열의 개수가 가장 많은 값을 출력해주면 된다.

 

 

코드구현

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

vector<int> narray;
vector<int> n_cnt(1000, 0);

int main() {
	int n, num, i, j, check, save_index;
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> num;
		narray.push_back(num);
	}


	for (i = 0; i < n; i++) {
		check = 1;   // 현재 값보다 작은 값이 있었는지 체크
		save_index = 0;   //0으로 초기화
		for (j = 0; j < i; j++) {
			if (narray[j] < narray[i]) {
				if (n_cnt[j] >= n_cnt[save_index]) {
					save_index = j;    //작은 값중에 cnt가 가장큰 위치 저장
					check = 0;
				}
				
			}
		}
		if (check == 1) {   //현재 값보다 작은 값이 없었으므로 cnt 1로 저장
			n_cnt[i] = 1;
		}
		else
		    n_cnt[i] = n_cnt[save_index] +1;   //자기자신과 큰 위치 값의 cnt를 저장해 더해줌

	}

	auto iter = max_element(n_cnt.begin(), n_cnt.end());  //cnt가 가장 큰 값 찾기
	cout << *iter;

	
}