소스를 대충 훑어보니 그리디로 푸신 것 같긴 합니다.. 사실. 조금 어려웠어요~^^
일단 음. 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가 자연수가 되게 하는 방법을 찾아보세요.
yth1130 7년 전