1965번: 상자넣기
정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가
www.acmicpc.net
1. 풀이방법
- 간단하게 생각하면 매우 간단합니다.
- 저 같은 경우 처음에 막혔던 부분이 보통의 dp문제에서 dp테이블은 각각의 n에 따른 정답? 을 가지고 있습니다.
- 이런식으로 짜려고 고민을 하다 보니 상당히 구현이 까다로웠습니다.
- 예를 들면 테스트케이스 가 1, 6, 2, 5, 7, 3, 5, 6 총 8개 인데
- 보통의 dp 테이블이면 만약 dp[6]을 뽑으면 최대치는 1,2,5,7 로서 4가 나와야 하고
- 이때의 상자의 바깥껍질의 크기인 7을 저장하면 dp[7]을 구하려고 할 때 1,2,5,7,과 1,2,3, +5 를 비교하는 것이 힘들었습니다.
- 설명하기가 조금 곤란한데, 비슷한 고민을 하신 분들은 공감을 하시리라....조심스럽게 생각해봅니다....
- 그래서 이 문제의 경우 n이하의 각각의 정답(즉 최대 상자의 수)를 dp에 저장하는 것이 아니라
- n에 크기를 늘려가면서 그때까지 차곡차곡 쌓기만한 크기를 저장해 놓은 다음 출력 전에 정렬을 해서 max 값을
- 출력하였습니다. 물론 정렬(소팅)을 하지않고 최대값만 갱신해도 상관 없습니다.
- 이런식으로 할경우 사실 정렬 전에 dp[6]에는 상자의 개수 3 (1,2,3) dp[5]에는 4 (1,2,5,7) 이 들어가 있습니다.
- 그러므로 n이 6일 때의 정답이 테이블에 들어가 있는 것은 아닌 것이죠. 정렬을 해서 출력을 해줘야 정답이 나오는
- 것 입니다. 하지만 이렇게 하면 문제의 요구사항에는 전혀 에러가 없고, 구현이 편해집니다.
2. 주의사항
- 위에 기재.
3. 나의코드
#include<bits/stdc++.h>
using namespace std;
int dp[1001]; // 사실상 정확한 dp를 가지고 있는 테이블은 아니다.
int n;
int narr[1001]; //상자의 크기
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) { //초기화
cin >> narr[i]; dp[i] = 1;
}
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (narr[i] > narr[j] && dp[i]<dp[j]+1) {
dp[i] = dp[j]+ 1;
}
}
}
sort(dp + 1, dp + (n + 1));
cout << dp[n];
return 0;
}'알고리즘 문제풀이 > 다이나믹 프로그래밍' 카테고리의 다른 글
| 백준 1103 [C++] (0) | 2021.07.06 |
|---|---|
| 백준 1793 [C++] (0) | 2021.02.04 |
| 백준 1463 [C++] - 메모리초과 (0) | 2020.12.15 |
| 백준 11048 [C++] (0) | 2020.12.14 |
| 백준 11726 [C++] (0) | 2020.12.14 |