[ALGORITHM] 백준 1965 - 상자넣기

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

1965번: 상자넣기

과정

1. dp를 1로 초기화 해준다.
2. 현재 위치 이전 값들과 비교하여 만약 num이 작은 경우 dp[now] 와 dp[prev] + 1을 비교 해준다.
3. dp[now]가 작은 경우 dp[prev] + 1을 해준다. 1은 현재 상자가 반영된 경우

생각해보기

비교된 값들 중 현재까지 비교했던 가장 큰 값을 저장을 해놓는다면 조금 더 빠른 속도로 돌아가는 대신 메모리를 더 사용하게 될 것 같다.

 

코드

#include<iostream>

using namespace std;

int n;
int dp[1001];
int nums[1001];

void input(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>nums[i];
        dp[i]=1;
    }
        
}

void solution(){
    int ret=0;

    for(int now=0;now<n;now++){
        for(int prev=0;prev<now;prev++){
            if(nums[now] > nums[prev])
                dp[now]=max(dp[now],dp[prev]+1);
        }
        ret=max(ret,dp[now]);
    }

    cout<<ret<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    input();
    solution();

    return 0;
}