8300 원을 모두 써서 800원짜리 사과와 900 원짜리 배를 최대한 많아 사려고 합니다. 가각 몇 개식 살 수 있숩니까?
친구가 보내준 문젠제 오학년 전과를 버려서 ;저걸 어떻게 초등 오학년식으로 설명해줄지 모르겠대요.
저는 800 과 900 의 배수로. 더해서 끝자리 300 이 나오는 순서쌍을 만든 뒤에 골라보라고 했는데 친구가 어떻게 해결봤는지 모르겠고, 친구는 단지 저를 괴롭히려고 보낸 혐의가 짙고 뭐 이렇습니다.
이런 거 보면 고민하느라 잠 설치는 성격인 거 아니까요.
오학년 과정에 뭐가 나오는지 모르니 질문이 좀 이상합니다만, 어떻게 설명하시겠어요? 답이 아니라 풀이 과정이 중요합니다.
초등 수준에서 부정방정식의 해법은 결국 순서쌍 일일이 만드는 방법 밖에 없을 것 같습니다.. 우선 가격이 900원인 배를 기준으로 배를 1개 사면 사과 9개.. 배를 2개 사면 사과 8개.. 이런 식으로 모든 순서쌍을 구한 다음, 최대값이 나오는 경우를 찾으면 되겠네요..
일단 최대한 많이 사려면 싼 걸 많이 사야함. 그러니까 일단 사과를 최대한 많이 삼. 사과 10개 -> 잔돈 300원 -> 배 못삼 -> 답 아님 사과 9개 -> 잔돈 1100원 -> 배 1개 -> 잔돈 200원 남음 -> 답 아님 사과 8개 -> 잔돈 1900원 -> 배 2개 -> 잔돈 100원 남음 -> 답 아님 사과 7개 -> 잔돈 2700원 -> 배 3개 -> 잔돈 없음 -> 답인가??
이건 경우의 수를 다 따져야죠. 배낭 알고리즘 문제입니다. 어떤 알고리즘을 쓰면 가장 빠르게 답을 얻을 수 있을 것인가만 설명하면 되죠. 그러나 이건 쪼갤 수 없는 NP-완전 문제에 속하므로 결국 경우의 수를 다 따져봐야 합니다. 합한 개수가 최대만 되면 된다면 사과로 모두 채우고 하나씩 비워 가면서 배를 채워 넣는 게 빠르겠죠.
문제수준이 일종의 반칙 같은데요 8a+9b=83(단위100원, a는 사과갯수, b는 배갯수) (a+b)=(83-b)/8 =>자연수 a+b를 최대로 하는 자연수 b를 찾으면 됨 83-b가 8의 배수이어야 하므로 b=3 따라서 a=7이 나오는데 6학년 수준으로 해야 맞을 것 같습니다
경우의 수를 따진다면 거스름돈이 없는 경우의 수를 모두 구하고 빠진 경우가 없다는 것을 증명한 후 최대갯수의 케이스를 답으로 작성해야 감점이 없을 것 같군요(대학수학의 경우라면)
제 전공분야가 아니라서 잘은 모릅니다만, Knapsack problem 은 주어진 돈을 남김없이 다 써야 한다는 조건이 *없을* 경우일텐데... 원글의 문제는 돈을 다 써야 한다고 했으니 그냥 정수해를 구하는 문제이죠. 그리고 댓글 중에 '쪼갤 수 있는 경우는 그리디 알고리즘'을 써야 한다고 하시고선, 원글의 문제는 쪼갤 수 없는 경우인데 그리디 알고리즘을 쓰셨네요. 그리고 "사과나 배는 꼭 하나는 반드시 사야한다" 는 조건은 어디서 나온건지 모르겠군요.
돈을 다 써야 한다고 해도 결국은 최적값을 구하는 문제죠. 나머지가 최소가 되도록 이라는 조건이고 최소는 결국 0원이니까요.
쪼갤 수 없는데 그리디 알고리즘을 썼기 때문에 운이 좋은 경우가 아니면 사용할 수 없습니다. 즉, 저 배의 값이나 사과의 값이 다른 숫자로 변하면 최적의 해를 구할 수 없는 경우가 생깁니다.
위에 제가 제일 처음 쓴 해법도 사실은 그리디 알고리즘이죠. 비싼 배를 먼저 산 다음 하나씩 버리고 나머지를 사과로 대체했으니까요. 두번째는 단지 하나는 꼭 사야한다는 조건을 붙여서 부분해의 범위를 넓힌 겁니다. 돈을 다 쓴다는 조건이 있다면 이미 사과나 배가 한개씩은 필요 (9나 8의 배수 중 83은 없으므로) 하다고 볼 수 있으니까요.
아, 그리고 그리디 알고리즘이나 Knapsack problem 을 언급한 건 답이 정해져 있어서가 아니라 답을 어떻게 빨리 찾느냐를 설명하기 위한 것입니다. 모든 경우를 다 구하거나 조합을 구해도 답은 나오는데, 그 답을 좀 더 빨리 구하는 방식이 알고리즘이라는 거죠.
