[소프티어] 징검다리 / C++ 해설

더 많은 문제풀이는 아래 Github 주소에서 확인하실 수 있습니다.

https://github.com/Dongha-k/softeer-code

GitHub - Dongha-k/softeer-code: softeer 문제 풀이입니다.

문제 출처: https://softeer.ai/practice/info.do?idx=1&eid=390 

Softeer

공식 해설: https://softeer.ai/community/view.do?idx=30&cd=edu&pageNo=1 

Softeer

#include <iostream>
#include <algorithm>

using namespace std;

int main(int argc, char** argv)
{
	int d[3000];
	int seq[3000];
	int n, max_d = 0;
	cin >> n ;
	for(int i = 0; i < n ;i ++){
		cin >> seq[i];
	}
	for(int i = 0 ; i < n ; i++){
		d[i] = 1;
		for(int j = 0 ; j < i ; j ++){
			if(seq[j] < seq[i]){
				d[i] = max(d[i], d[j] + 1); 
			}
		}
		max_d = max(max_d, d[i]);
	}
	cout << max_d;
	
	return 0;
}

 

LIS(가장 긴 증가하는 부분 수열) 문제이다.