백준 1965 [C++]

www.acmicpc.net/problem/1965

1965번: 상자넣기

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;
}