퀴즈35는 최적화 문제와 관련된 유명한 문제를 각색한 것이다.

먼저 문제를 살펴보자

퀴즈 35

어느 채굴장에 A,B,C,D 4 개의 컴퓨터가 있다. A 는 하루에 스팀 8개를 채굴하거나 스팀달러 10 개를 채굴한다. B 는 하루에 스팀 9개를 채굴하거나 스팀달러 12개를 채굴한다. C는 하루에 스팀 7개를 채굴하거나 스팀달러 11개를 채굴하고, D는 하루에 스팀 6개를 채굴하거나 스팀달러 7개를 채굴한다.

자 이 채굴장에서는 스팀과 스팀달러 갯수를 서로 맞춰 만든다고 하자.
그리고 나는 이 (스팀, 스팀달러) 가 매칭되는 쌍만큼 EOS 를 구입한다고 하자.

일주일 동안 이 4개의 컴퓨터로 스팀과 스팀달러를 채굴한다고 할 때, 나는 최대 몇개의 EOS 를 구입해야 하는가?

풀이

이 문제의 핵심은 어떻게 하면 스팀과 스팀달러 쌍의 갯수를 최대로 하느냐에 달려있다.

원래의 아이디어는 "하루에 steem 을 가장 많이 채굴하는 컴퓨터가 steem 을 채굴하게 하고, 스팀달러를 가장 많이 채굴하는 컴퓨터로 스팀달러를 채굴하게 하면 그 쌍을 최대로 만들 수 있다." 에서 시작한다.

[최적화 문제 중 하나이다]

스팀은 9, 8, 7, 6 개를 뽑을 수 있고

스달은 12, 11, 10, 7 개를 뽑을 수 있다.

전체적으로 스달이 스팀보다 많이 뽑힐 수 있기에 스팀을 많이 뽑는 방향으로 진행해야 스달과 스팀의 균형을 맞추기 쉽다.

그런데 문제는 B가 스팀과 스팀달러 모두 최대로 많이 뽑는다는 것! 이 것이 이 문제가 어려워지는 조건이다.

B는 하루에 스팀(9개) 혹은 스달(12개)을 만들 수 있다. [둘다 최대]

A는 하루에 스팀(8개) 혹은 스달 (10개)를 만들 수 있다.

쌍의 갯수가 최대라... 이 말 전체 갯수가 한정되어 있기에, 그 쌍을 최대로 한다는 말은 즉 스팀양=스달양 이 되도록 한다는 것과 같아진다. [비슷한 논리를 이전 삼각형 포스팅에서도 한 적이 있다]

스팀에서는 6을 7일간 뽑고, 스달에서는 (스팀의 9가 12랑, 8이 10이랑 대응되니) 11을 7일간 뽑고 나머지를 변수로 A 가 스팀만 채굴하는 날을 x ( 그러면 A 가 스달만 채굴하는 날은 7-x 가 된다) B 가 스팀을 채굴하는 날짜를 y (그러면 B 가 스달만 채굴하는 날은 7-y) 로 하고 일주일간 채굴된 스팀과 스달양을 같게 식을 만들어보자

얘를 y에 대해서 풀면

이를 pair의 수에 다시 넣어보면

이 때 x 는 0에서 7 사이의 값을 가지니 x=7, y=3 일 때 최대값 125를 가진다. [다른 방식으로 해보면 이 값이 125보다 작게 나온다]

즉 나는 125개의 EOS 를 사야한다.