gunilyang   1년 전

인터넷에 있는 0-1배낭문제 소스를

문제에 맞게 수정했는데

예제랑 몇몇 케이스 테스트해보면 맞게 나오는데

제출시 틀리다고 뜨네요...

다른 함정이 있는건가요...?

무게 리미트 99로 한 배낭문제 아닌가욧!????

baekjoon   1년 전

Dynamic Programming (동적계획법)을 이용해서 풀 수 있네요.

문제에 주어지는 조건이 3개이고, 지구하려고 하는 값이 최대 기쁨이기 때문에 2차원 DP를 다음과 같이 정의할 수 있겠네요.

또, 인사하는 순서는 상관없기 때문에, 0번부터 차례대로 인사를 한다고 가정할 수도 있겠네요. 문제에는 1번부터 사람의 번호를 세지만, 설명에서는 0번부터로 하겠습니다.

D[i][j] = i번 사람과 인사하려고 하고 (i-1번 사람까지는 인사를 할지, 안 할지를 결정했음), 그 때 체력이 j일때 얻을 수 있는 최대 기쁨

이제 각각의 사람마다 세준이는 인사를 할지 안할지를 결정해야 합니다.

인사를 하는 경우는 D[i+1][j-L[i]] + J[i] (j-L[i] > 0)이고, 인사를 하지 않는 경우는 D[i+1][j]가 됩니다.

따라서, 메모이제이션을 이용해서 아래와 같이 코딩할 수 있습니다.

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