글 읽기 - 보석 모으기 어디서 잘못된건지 모르겠어요..

astrohsy 8년 전 0

경우가 3가지 밖에 없는 것 같아서 저렇게 재귀적으로 DP를 구현했는데

리젝트가 나오네요..

놓친 경우가 무엇이 있나요???

#include <iostream>
#include <vector>
#define MAX(X, Y) ((X) > (Y)) ? (X) : (Y)
using namespace std;

int N, M, C;

int dp[30][30][30];
vector<int> jewerly;

int get(int numOfJew, int leftBag, int leftSize, int n)
{
	if( n == N+1 )
		return numOfJew;

	if( leftBag == 0 )
		return numOfJew;

	int *ret = &dp[leftBag][leftSize][n];
	if(*ret)
		return *ret;

	if( leftSize < jewerly[n])
		return	*ret= MAX( get(numOfJew, leftBag, leftSize, n+1), get(numOfJew, leftBag-1, C, n));          

	return *ret = MAX(	get(numOfJew, leftBag-1, C, n),                   //가방 바뀌는 경우
				  MAX(	get(numOfJew+1, leftBag, leftSize-jewerly[n], n+1),//보석을 담는 경우
						get(numOfJew, leftBag, leftSize, n+1)));           //안담는 경우
}

int main()
{
	cin >> N >> M >> C;
	jewerly.resize(N+1);
	for(int i = 1; i<=N; i++)
		cin >> jewerly[i];

	cout << get(0, M, C, 1) <<endl;
	
}

chatterboy 8년 전 1

저의 경우는 dp 정의를

T(p, w, s) = p번째 가방의 현재 무게가 w이고, 보석의 상태가 s일 때 가져갈 수 있는 최대 보석의 수

로 하고 풀었습니다.

보석의 상태 s는 비트로 표현했습니다.

astrohsy 8년 전 0

보석의 상태는 모든 보석에 대해서 가져갔는지 안가져갔는지 표현한 것인가요?

까다로운 문제네요..

chatterboy 8년 전 1

@astrohsy

네 모든 보석의 상태를 표현했습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

보석 모으기 어디서 잘못된건지 모르겠어요..

astrohsy 8년 전 0

chatterboy 8년 전 1

astrohsy 8년 전 0

chatterboy 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말