BaekJoon 1965번: 상자 넣기(C++)

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

1965번: 상자넣기

풀이법

1) 전형적인 DP 문제로, 이전의 값 중 자기 보다 작은 값 중 현재 dp배열의 값이 가장 큰 값+1을 자신의 dp 값으로 가져가면 되는 문제이다.

2) 초기 dp배열을 1로 만들어 주어야 한다는 점이 중요하다.

 

5

4 5 1 2 3

dp를 처음에 0으로 초기화 하게되면

1 2 0 1 2 라는 dp 배열이 나와서 오류가 나게 된다.

고로 dp 배열을 처음에 1로 초기화 하는 것이 매우 중요하다.

 

#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#define INF 987654321
using namespace std;

int n;
vector<int> vec;
int dp[1001];
int maxNum = 0;
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		vec.push_back(a);
		dp[i] = 1;
	}
	for (int i = 1; i < n; i++)
	{
		
		for (int j = i-1; j >= 0; j--)
		{
			if (vec[j] < vec[i])
			{
				dp[i] = max(dp[i],dp[j] + 1);
			}
		}
		maxNum = max(maxNum, dp[i]);
	}
	cout<<maxNum;
	
}