[백준/C++] 14231 박스 포장

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

코드

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

#define FASTIO ios::sync_with_stdio(false);cin.tie(NULL);

int main() {
	FASTIO;
	int n, ans = 0;
	cin >> n;
	vector<int> v(n);
	vector<int> dp(n, 1);

	for (int i = 0; i < n; i++) cin >> v[i];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (v[j] < v[i])
				dp[i] = max(dp[i], dp[j] + 1);
		}
		ans = max(ans, dp[i]);
	}
	cout << ans;
	return 0;
}

설명

현재 위치에서 이전 박스들을 모두 확인해주면서 조건에 맞을 때마다 dp[i]를 업데이트해줍니다.

 

느낀 점

식 찾기와 구현 모두 어렵지 않았습니다!