[백준] 1965번 상자넣기
[백준] 1965번 상자넣기
문제 링크: https://www.acmicpc.net/problem/1965
문제
입출력
문제 접근
dp문제이다. 그리고 단순히 LIS(최장 증가 수열)을 적용하면 되는 문제이다.
코드 구현(c++)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int cache[1001];
int box[1001];
int N;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
cin >> N;
for(int i = 0 ; i < N ; i++){
cin >> box[i];
}
int maxNum = -1;
for(int i = 0 ; i < N ; i++){
cache[i] = 1;
for(int j = 0 ; j < i ; j++){
if(box[j] < box[i]){
cache[i] = max(cache[i], cache[j] + 1);
}
}
maxNum = max(maxNum, cache[i]);
}
cout << maxNum << "\n";
}
Author And Source
이 문제에 관하여([백준] 1965번 상자넣기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kpg0518/백준-1965번-상자넣기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)