Home [알고리즘][백준] 음식평론가
Post
Cancel

[알고리즘][백준] 음식평론가

[알고리즘][백준] 음식평론가

명제

소시지 N개를 M명에게 공평히 나눠주기 위해 소시지를 자르는 최소 횟수는 M - gcd(N, M)이다.

증명

\[ Suppose\;that\;N\;=\;M.\ \] \[ Then\;We\;don’t\;need\;to\;cut\;sausages.\ \] \[ So,\;minimum\;cut\;is\;0\;=\;M\;-\;M\;=\;M\;-\;gcd(N, M) \]
\[ Suppose\;that\;N\;<\;M.\ \] \[ Let\;x\;=\;gcd(N, M).\ \] \[ Then,\;there\;exist\;a\;and\;b\;s.t.\;N\;=\;ax\;and\;M\;=\;bx,\;gcd(a,\;b)\;=\;1.\ \] \[ Since,\;each\;person\;should\;get\;N\;/\;M\;sausages,\;N\;/\;M\;=\;a\;/\;b.\ \] \[ Let\;y=\max \{l \in \mathbb{N} | {a \over b} \times l \leq 1 \}\;be\;a\;maximum\;cut\;of\;each\;sausage. \] \[ \Rightarrow {b \over a} - 1 < y < {b \over a} \] \[ \Rightarrow b - a < ay < b \] \[ \Rightarrow (\#\,of\,cut) = b - 1 \] \[ \therefore x(\#\,of\,cut) = xb - x = M - x = M - gcd(N, M) \]
\[ Suppose\;that\;N\;>\;M.\ \] \[ Then,\;We\;can\;provide\;N//M\;sausages\;without\;cuts.\ \] \[ So,\;We\;should\;cut\;N\;mod\;M\;sausages\;for\;M\;people.\ \] \[ Since\;N\;mod\;M\;must\;be\;lower\;than\;M,\;from\;above\;proof,\;it’s\;done.\square \]

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
def sol():
    N, M = map(int, input().split())
    print(M - gcd(N, M))


def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


if __name__ == "__main__":
    sol()
This post is licensed under CC BY 4.0 by the author.

Daily Commit 분포 확인하기

Daily commit - 1년 회고