shjoo840   2년 전

test case는 다 통과했는데 제출하면 9%에서 틀렸다고 나옵니다. 

디버깅 하기 쉽지 않을 코드일 것 같지만 혹시나 시간 남으실 때 봐주시면 감사하겠습니다.


알고리즘은 다음과 같습니다.

1. 변수 : list A, B

A에는 가격이 들어갑니다.

B가 핵심인데, B[i]에는 i번째 까지의 세트 (i=0 to n-1) 중 가장 가성비가 좋은 세트의 번호가 들어갑니다.

예를 들어 가격 인풋이 [1,1,4,3,10] 이라면 B는 다음과 같습니다.

B = [0,0,2,2,4] 


2. 함수 x

함수 x는 가격을 반환합니다. 재귀함수 구조이며

x의 인풋 중 n은 팔아야 하는 붕어빵의 갯수를 뜻합니다. A,B는 그냥 list를 전달하기 위해 사용했습니다.

대략적으로 설명드리자면 l= 남은 n개의 상품 중 가성비가 가장 좋은 set를 뜻합니다.

n/(l+1)은 l세트로 몇개를 팔아야 하는지를 뜻하며 거기에 가격인 A[l]을 곱하면 l세트로 판 금액입니다.

n을 l+1개로 팔고 나면 남는 붕어빵이 n%(l+1)이므로 다음 함수의 인풋으로 넣어줍니다.


이런식으로 코드를 짰는데 실패합니다. 

jh05013   2년 전

가성비가 좋은 옵션을 계속 선택하는 것이 최적해는 아닙니다.

shjoo840   2년 전

정말 감사드립니다. 덕분에 맘 편히 시험공부 하러 갑니다.

주신 반례는 13번 줄에 <를 <=로 바꾸면 풀리긴 하는 것 같습니다. 다른 반례를 찾아보았는데

4

1 5 8 4 

이런 케이스는 가성비가 각각

1 2.5 2.6 1이니 

8+1=9가 선택되네요.


감사합니다.

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