[C++] 백준 1965번 상자넣기

 

 

다이나믹 프로그래밍 문제.

어렵게 생각 안하고 풀었는데 틀렸습니다. 를 엄청많이 받고서야 풀었다.

그냥 완전탐색 비슷한 DP 느낌의 문제였다.

 

문제풀이

내가 푼 방식은 다음과 같다.

 

1번째 상자 ~ N번째 상자를 탐색한다.

i번째 상자를 탐색하면서 자기 앞에 있는 상자들(1 ~ i)

중 가장 많이 담을 수 있는 상자를 골라서 + 1 해준 후 현재 상자가 최대

이만큼 담을 수 있다는 것을 기록해놓는다.

 

상자들 중 몇번째 상자가 가장 많이 기록할 수 있는지 출력한다.

 

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

int boxCnt;
int boxSize[1001];
int dp[1001];
int ans = 1;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> boxCnt;

	for (int i = 1; i <= boxCnt; i++) {
		cin >> boxSize[i];
	}

	for (int i = 1; i <= boxCnt; i++) {
		dp[i] = 1; // 틀린이유, 하나만 넣는 거 고려안했음.
		for (int j = 1; j < i; j++) {
			if (boxSize[j] >= boxSize[i]) { continue; }
			dp[i] = max(dp[i], dp[j] + 1);
		}
		ans = max(ans, dp[i]);
	}

	cout << ans;

	return 0;
}

코드 전문.

처음 N를 입력받은 후에 N개 상자의 사이즈를 입력받는다.

 

그리고 1 ~ N까지 상자를 위에 설명한대로 탐색한다.

이중 for문을 돌려도 최대 O(N^2), 상자가 최대 1,000개 이므로

최악의 경우 최대 1,000,000번의 연산이 필요하다.

앞에 있는 자기 속에 넣을 수 있는 상자들 중 자기 속에 넣었을 때 가장 많이 담게되는

상자를 골라서 기록해준다.

그리고 ans와 기록한 값 중 더 큰 값을 ans에 기록한다.

이 때 틀린이유가 있는데, 아무것도 넣지 못할 때엔 자기 자신만 존재하므로 1이여야 한다.

이걸 생각을 못했다...

 

ans를 출력한다.

 

 

GitHub - kimyunseok/cpp: my study-record

코드 전문은 위에서도 확인이 가능하다.