< 백준 BaekJoon : 11053번 가장 긴 증가하는 부분 수열 > C++

<< 문제 >>

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

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

 

 각 위치를 마지막으로 하는 수열의 크기를 저장하고,

이어지는 수들이 다 지난 수 중 작은 숫자 중 수열이 최대가 되는 값에 +1을 해주면 됩니다.

 

말은 좀 어려운데 코드로 보면 이해가 쉽습니다.

 

 

<< 코드 >>

#include <iostream>
using namespace std;

int main() {

	int num;
	cin >> num;

	int input[1000];
	for (int i = 0; i < num; i++) {
		cin >> input[i];
	}

	// 각 위치를 마지막으로 하는 수열의 크기를 저장
	int val[1000] = { 0, };
	for (int i = 0; i < num; i++) {
		for (int j = 0; j < i; j++) {
			if (input[j] < input[i]) { // 
				if (val[i] <= val[j]) {	 // 더 큰 수열을 발견했을때만
					val[i] = val[j] + 1;
				}
				
			}
		}

		if (val[i] == 0) {
			val[i] = 1;
		}
	}

	int max = val[0];
	for (int n: val) {
		if (n > max) {
			max = n;
		}
	}

	cout << max;
}

 

 

<< 깃헙 >>

 

https://github.com/J2on/StudyAlgorithm_Part2/tree/main/%EB%B0%B1%EC%A4%80/Silver/11053.%E2%80%85%EA%B0%80%EC%9E%A5%E2%80%85%EA%B8%B4%E2%80%85%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94%E2%80%85%EB%B6%80%EB%B6%84%E2%80%85%EC%88%98%EC%97%B4