yth1130   7년 전

모든 케이스가 다 잘 되는거 같은데 뭐가 틀린걸까요 고수님들!

chogahui05   7년 전

소스를 대충 훑어보니 그리디로 푸신 것 같긴 합니다.. 사실. 조금 어려웠어요~^^

일단 음. 3kg짜리 설탕 봉지 갯수가 3개 이하일 거라. 이래 가정하시고 푸시는 것이지요?

3x + 5y = input

x + y = k

이렇게 두 개의 식을 세워서 적절히 풀어주면

#1. k = (input + 2x) / 5 

가 나오게 됩니다. 물론, 이 k가 최소가 되는 값을 찾아야겠죠.

물론, input, x, k는 모두 정수이기 때문에 이 셋 중 하나가 소수가 나오면 안 되겠죠..


input이 32라고 해 봅시다.

32 (27) - 27 (22) - 22 (17) - 17 (12) - 12 (7)

7 (2) 2<5이므로, 4고요. 이후부터 3씩 빼겠죠.

그 경우에 최종적으로 -1이 리턴이 되지요.


자. 그런데 말이지요. 32kg를 3kg, 5kg로 나누는 방법이 없을까요?

3kg짜리 9개, 5kg짜리 1개로 나눌 수 있습니다.


이 반례가 왜 생기냐면

yth님께서 3kg짜리 설탕 갯수는 3개 이하로 운반하면 최적일 거야~ 이렇게 가정하셔서 그런데요.

당장 input = 32를 #1에 넣어보면 알 수 있지요.

k = (32 + 2x)/5 이지요?

x가 0이상, 3이하일 때, k가 자연수가 되게 하는 방법을 찾아보세요.

allkanet72   7년 전

652 하면 132 나와야 정상입니다. 위 코드는 -1 나오네요 

yth1130   6년 전

답변달아주신분들 감사합니다!

예전에 물어봤던 글인데 읽고 답글단다는것을 깜빡했네요;;

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