백준 C++ | #23 BOJ11053 계단 오르기 C++ 문제 풀이

11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net)

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

 

다이나믹 프로그래밍 문제였다. 

다이나믹 프로그래밍을 푼 두번째 문제였는데, 다이나믹 프로그래밍은 배열을 하나 더 만들어서 재귀 대신 쓰는 방식인 것 같다. 이 문제에서도 복잡하게 생각할 것 없이 수열 사이즈에 맞는 배열을 하나 더 만들고, 배열마다 그 사이즈를 다른 배열을 이용해 저장해주었다. 

몇 번 틀렸는데, 그건 배열의 최댓값 원소가 아니라 배열의 마지막 원소를 출력하도록 해서 그런 거였다. 

 

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

int main() {
	int n;
	std::cin >> n;
	std::vector<int> a;
	std::vector<int> c(n);
	for (int i = 0; i < n; i++) {
		int tmp;
		std::cin >> tmp;
		a.push_back(tmp);
	}

	// 가장 긴 증가하는 부분 수열
	for (int i = 0; i < n; i++) {
		c[i] = 1;

		for (int j = 0; j < i; j++) {
			if (a[j] < a[i] && c[i] < c[j] + 1) {
				c[i] = c[j] + 1;
			}
		}
	}

	
	std::cout << *std::max_element(c.begin(), c.end()) << std::endl;
	return 0;
}