allgoodlife   7년 전

붕어빵 문제를 어떻게 DP로 접근할 지 잘 생각이 되지 않아서 제 나름의 방법으로 풀어보았습니다.

제 접근 방식은 간단히 설명드리면 다음과 같습니다.

1.개당 가격이 비싼 세트별로 multimap을 구성한다.

2. (붕어빵의 개당 가격)이 가장 비싼 세트부터 가장 싼 세트까지 판매한다. 개당가격이 높은 세트를 팔 수 있을 때까지 판매하고 그 후에는

3. 다음 개당가격이 높은 붕어빵세트를 판매한다.

4. 만약 이 과정을 다 거쳤는데도 남은 붕어빵의 갯수가 0개 되지 않는다면 2-3 과정을 반복한다.


제 질문은 다음과 같습니다.

1. 테스트 케이스 6개는 모두 맞게 나오는데 어느부분에 오류가 있는 지 알려주세요~

2. 이런 접근방법에 대해서 어떻게 생각하시는지와, 이런 문제를 풀 때 어떻게 dp로 접근해야 하는 지 알려주세요~


프로그래밍 공부를 시작한 지 얼마 안되다 보니 내공이 부족하네요~ 고수님들의 조언 부탁드립니다.

supercom   7년 전

yohan5050님의 글에서 발췌한 내용입니다.


/***************

제가 예시를 실행해봤는데요,

10
1 2 8 10 11 12 13 14 15 16 
이 경우 3set+ 3set + 4set해서 26이 최대값인데, 질문자님의 코드에서는 25가 나오는 것 같습니다.

*******************/

직접 실행해보아도 25가 뜹니다.

왜그런지는 저도 잘 몰라요(저도 초짜...^^;;)

atomzeno   7년 전

아마 전형적인 n2 dp 일 겁니다

d[i]: i개를 세트로 최적으로 잘 팔때 최적의 해로 두면

d[i]=max(d[j]+S[i-j],d[i]) 로 식이 세워져서 계속 돌리면 될 듯합니다.

atomzeno   7년 전

추가적으로, map을 사용하는 기법도 위의 방법과 거의 유사하게 짤 수 있습니다.

allgoodlife   7년 전

도움주신분들께 감사드립니다. 다시한번 짜보겠습니다.

allgoodlife   7년 전

supercom님 께서 달아주신 댓글을 바탕으로 시뮬레이션 해보니, 뭐가 문제인 지 찾았습니다. 비슷한 문제로 고민하는 분들을 위해 남깁니다.

우선 제가 푼 방식은 당장에 '개당 판매가격이 높은 붕어빵'부터 세트로 파는 전략이었는데,

이는 부분의 최적해가 전체의 최적이 되는 Greedy문제일 때 적합합니다.

이 문제는

sum(부분의 최적해) = 전체의 최적해

라는 보장이 없기에 Greedy 방법이 틀린 것이고, 위 반례가 이를 보여줍니다.

예를 보면, 당장의 최적의 해인 3개짜리 세트를 3세트 팔았지만, 2세트만 팔고 4개짜리 세트를 파는 게 최종 이윤을 극대화하였습니다.

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