BOJ 7619 Restaurant tab

지폐와 동전을 편의상 “동전"이라고 합시다. 일단 각자가 갖고 있는 동전들을 모두 모은 다음 각자가 마지막에 가져야 할 금액만큼씩 재분배한다고 생각합니다.

1센트 동전 이외의 모든 동전은 5의 배수이므로, 각자 필요한 금액을 5로 나눈 나머지가 0이 아니라면 그만큼은 무조건 1센트 동전으로 채워야 합니다. 그러고 나서 남는 1센트 동전이 있다면, 이들을 5개씩 묶어 5센트 동전과 똑같이 취급할 수 있습니다. 이후에도 남아있는 최소 단위를 제외한 모든 동전이 다음 단위의 배수일 경우에는 이 그리디를 쓸 수 있습니다. 이를 Easy 그리디라고 합시다.

문제는 5센트, 10센트, 25센트 동전의 처리입니다. 편의상 5로 나누어 단위 없이 1, 2, 5라고 하겠습니다. (나중에 10, 20, 50달러에서도 똑같이 적용됩니다.) 이는 여러 가지 방법이 있는데, 두 가지 방법을 소개합니다.

• 5로 나눈 나머지로 분류하여 1과 2를 우선 처리하는 방법 (bubbler의 풀이)

원하는 금액을 5로 나눈 나머지가 0이 아닌 것은 1, 2, 3, 4가 있을 수 있습니다. 이 중에서 2, 3, 4의 경우, 2짜리 동전이 남아있다면 이를 우선으로 사용하여 나머지를 0이나 1로 만들어 주는 것이 이득입니다. 다른 모든 방법은 2 하나 대신 1을 두 개 사용한 것과 같기 때문입니다. 이 과정에서 2짜리 동전이 고갈된다면 남아있는 동전을 가지고 Easy 그리디를 하면 됩니다.

만약 원하는 금액이 정확히 1만 남은 사람이 있다면, 그 사람에게는 우선적으로 1짜리 동전을 줘야 합니다.

그렇지 않다면, 이제 10으로 나눈 나머지를 고려합니다. 이러한 나머지는 1, 5, 6이 있습니다. 1과 6의 경우, 1을 하나 받거나 2를 세 개 받으면 5의 배수가 됩니다. 2를 세 개 묶음으로 쓰지 않는 방법은 최적이 아닙니다. 그리고, 나머지 1인 상태에서 2를 세 개 받거나, 나머지 6인 상태에서 1을 받게 되면, 나머지 1이 1을 받는 것이나 나머지 6이 6을 받는 것과 비교할 때 5가 한 개 더 필요해집니다. 따라서 나머지에 맞게 사용하는 것을 우선으로 합니다.

이를 모두 처리했다면, 남은 값은 모두 5의 배수입니다. 이제 남은 1과 2 동전을 조합하여 5와 10으로 만들어서 다음 과정으로 넘기면 됩니다. 5를 우선으로 만드는데, 5를 만들기 위해서는 1이 반드시 필요합니다. 따라서, 1+2+2를 우선으로 처리하고, 그 다음 1+1+1+2, 그 다음 1+1+1+1+1과 2+2+2+2+2의 순서대로 묶음을 만들어주는 것이 최적입니다.

• 2로 나눈 나머지로 분류하여 1과 5를 우선 처리하는 방법 (공식 해답 코드의 풀이)

홀수를 10으로 나눈 나머지는 1, 3, 5, 7, 9가 있습니다. 이 중에서 5를 사용하는 것이 이득인 경우는 5, 7, 9입니다. 그렇지 않다면 불필요한 2가 더 소모되기 때문입니다.

그다음 1짜리 동전을 배정하는데, 앞의 다른 풀이와 마찬가지로 값이 절대적으로 작을 때 (정확히 1, 3일 때)에 1을 우선적으로 소비하고, 그 외의 나머지가 1, 3인 경우에 1을 하나씩 소비해 줍니다. 정확히 1, 3인 경우를 제외하고, 한쪽 동전이 부족하다면 다른 종류로 처리해 줍니다.

이 시점에서 1과 5 중에서 한 가지 동전만 남았다면 두 개씩 묶어 짝수 묶음으로 만들고 Easy로 넘기면 됩니다. 그렇지 않은 경우에는 5+1의 사용을 고려해야 합니다.

이 6짜리 묶음은 먼저 6이나 8에 사용해 줄 수 있습니다. 그리고 이러한 묶음을 한 사람에게 두 번 주는 것은 5+5와 1+1을 따로 준 것과 같으므로, 이 경우는 무시할 수 있습니다. 이러한 묶음을 2나 4에게 주는 것은 필요한 2의 개수에서 손해를 보게 되므로 주지 않고, 남은 2와 1+1을 만들어 모두 10의 배수로 만들어 줍니다.