백준1965 - 상자넣기

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

1965번: 상자넣기

동적 계획법을 사용한 문제다. 전에 내가 풀어봣던 동적 계획법과 다른 점이 있던 문제다. 전에 있던 동적 계획법들은 과정이 진행될 수록 값이 누적되어 다음에 있는 동적 계획값이 커졌는데 이 문제는 현재를 기점으로 가능한 많은 수의 우원소를 골라야하는 문제였다. 굉장히 도움이 된 문제였고 동적 계획시 반드시 다음 값이 커질 필요가 없다고 느끼게 해준 문제다. 반드시 풀어보자

#include <iostream>
#include <vector>
using namespace std;

int mat[1001][1001];

int main() {
	int n; //원소의 갯수
	int num; //원소
	vector<int> v; //원소를 담아둘 공간
	vector<int> ans; //DP값을 저장할 공간
	int res = -1; //가장 큰 값

	//DP값 세팅을 현재 원소를 하나 먹는 걸로 시작하고 현재 원소 값을 세팅
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num;
		v.push_back(num);
		ans.push_back(1);
	}

	//현재 인덱스를 기준으로 최대로 먹을 수 있는 상자의 수를 센다.
	for (int i = 0; i < n; i++) {
		int check = 1; //시작은 나 자신 한 개 먹기

		for (int j = i - 1; j >= 0; j--) { //나 자신을 제외한 바로 뒤에 상자부터 찾아간다.
			if (v[i] > v[j]) { //나보다 작은 상자를 만나면
				if (check > ans[j] + 1) { //과거의 먹은 상자의 총 갯수가 현재까지 먹은 상자의 수보다 많으면
					continue; //무시
				}
				check = ans[j] + 1; //과거의 먹은 상자의 수를 현재까지 먹은 상자의 수로 대체
			}
		}

		ans[i] = check; //현재까지 먹을 수 있는 최대의 상자 갯수

		//최댓값을 찾는 과정
		if (res < ans[i]) {
			res = ans[i];
		}
	}

	cout << res;
}