백준 1965 상자넣기 쉬운 풀이 (C++/CPP)

문제링크 : https://www.acmicpc.net/problem/1965

문제 추상화

• 점점 커지는 연속하지 않아도 되는 수열 구하기
• LIS 문제와 같음
  • LIS 개념 : https://www.acmicpc.net/problem/11053

아이디어

• N의 크기가 작으니까 DP로 해결
  • DP[X] = X 위치에서 한번에 넣을수 있는 상자 개수의 최대값
    • 점화식
  • DP[X] = max(if(arr[x] > arr[i]) DP[i]+1)
  • 순회 돌면서, 상자의 값이 더 클경우, DP값+1의 최대값

시간복잡도 계산

• 각 노드에서 이전 노드 모두 돌아야함 : O(N^2) > 1e6

인트 계산

• DP값 : 최대 1000 > INT 가능

코드

#include <iostream>
 
using namespace std;
 
int dp[1010];
int map[1010];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    
    int maxv = 1;
    
    int N; cin >> N;
    fill(dp, dp+N, 1);
    for(int i=0; i<N; i++) cin >> map[i];
    
    for(int j=0; j<N; j++) {
        for(int i=0; i<j; i++) {
            
            if(map[j] > map[i]) {
                dp[j] = max(dp[j], dp[i]+1);
                maxv = max(maxv, dp[j]);
            }
        }
    }
    
    cout << maxv << '\n';
    return 0;
}
 

문제유형

• DP - LIS
  • DP에서 순차적으로 오는것이 아닌, 여러 경로가 있을떄 사용
  • 특히 2차원에서 상하좌우를 모두 고려해줘야할 때

비슷한 문제

• https://www.acmicpc.net/problem/9251
• https://www.acmicpc.net/problem/2565
• https://www.acmicpc.net/problem/1965