BOJ 1965번 <상자 넣기>
난이도 :실버 2
알고리즘 분류 :DP
우선 DP 배열을 하나 생성한다.
i 번째 원소까지 담을 수 있는 상자의 최대 갯수를 저장한다.
여기서 초기값으로 dp[i] = 1 를 설정해줘야 한다. 자기 자신을 선택하는 순간 상자의 갯수는 최소 1개가 되기 때문이다.
상자 크기를 저장해둔 배열을 탐색한다. 다만 i 번째 상자에 담을 수 있는 상자를 탐색한다.
그래야지 값 갱신에 유의미하기 때문이다.
1~ i-1 번째 상자들 중 i 번째 상자에 담을 수 있는 상자들이 담을 수 있는 최대 상자의 갯수
(dp[1] ~ dp[i-1]) 와 비교하여 dp[i] 보다 큰 경우 dp[i] 의 값을 비교값 + 1 로 갱신한다.
int N;
int map[1001];
int dp[1001];
void input() {
for (int i = 1; i <= N; i++) {
cin >> map[i];
}
}
void solve() {
int max = 0;
for (int i = 1; i <= N; i++) {
dp[i] = 1;
for (int j = 1; j < i; j++) {
if (map[j] < map[i]) {
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
}
}
}
if (dp[i] > max) {
max = dp[i];
}
}
cout << max << endl;
}
int main() {
cin >> N;
input();
solve();
}
어떤 의미로는 주어진 수열 중 가장 긴 증가하는 부분수열 을 구하는 문제이기도 하다.
패턴을 기억해두자.