[백준][1965번] 상자넣기

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

1965번: 상자넣기

 

풀이과정

 

오름차순 부분배열을 구하는 문제이다.

 

dp[N]은 map[N]을 포함하는 가장 큰 부분배열의 길이이다.

 

map[N]보다 작은 값을 가지면서 가장 큰 길이를 가진 부분배열의 + 1 한 값을 누적하면서 최댓값을 구하면 된다.

 

 

 

소스코드

#include <stdio.h>
#include <algorithm>
using namespace std;

int dp[1001];
int map[1001];
int N;

int solution() {
	dp[0] = 1;
	int answer = 1;
	for (int i = 1; i < N; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++) {
			if (map[j] >= map[i]) continue;

			dp[i] = max(dp[i], dp[j] + 1);
		}
		if (answer < dp[i]) {
			answer = dp[i];
		}
	}
	return answer;
}

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &map[i]);
	}

	printf("%d\n", solution());
	return 0;
}