프로베니우스의 동전 문제(Frobenius coin problem)와 슈어의 정리(Schur's theorem)

1. 프로베니우스의 동전 문제(Frobenius coin problem)

 

서로 다른 두 동전 x원, y원이 있을때, 이 두 동전을 각각 적당한 개수를 사용하여, 만들 수 없는 금액중 가장 큰 값은?

 

이 문제의 정답을 프로베니우스의 수(Frobenius number)라고 부른다.

 

예를 들어 3원, 5원짜리 동전으로 만들 수 없는 가장 큰 금액은 7원이다.

 

이 말은 8원 이상의 금액은 무조건 만들 수 있다는 뜻이다.

 

주의할 점은 7원 밑의 금액 중에서 1,2,4원은 만들 수 없다는 것은 자명하다.

 

프로베니우스의 수는 x,y가 서로소(최대공약수가 1)일때만 존재한다.

 

이때, 프로베니우스의 수는 xy - x - y임이 알려져있다.

 

 

2. 일반화된 문제

 

일반적으로는, n개의 동전 $a_{1}, a_{2},..., a_{n}$이 있고, 이들의 최대공약수가 1일때,

 

$$k_{1}a_{1} + k_{2}a_{2} + ... + k_{n}a_{n}$$으로 만들 수 없는 가장 큰 양의 정수는 얼마인가?

 

이 문제의 정답을 프로베니우스의 수라고 부른다.

 

n이 2일때는 명확한 공식이 위에서 언급한 대로 존재하지만, n이 3 이상일때는 명확한 공식이 존재하지 않고 구하는 방법이 알려져있지 않다.

 

 

3. 프로베니우스의 수는 존재하는가?

 

프로베니우스의 수는, $a_{1}, a_{2},..., a_{n}$의 최대공약수가 1인가 아닌가에 따라 존재 여부가 달려있다.

 

실제로 $k_{1}a_{1} + ... + k_{n}a_{n}$이 만들 수 있는 수는 $a_{1}, ..., a_{n}$의 최대공약수의 배수이다.

 

이는 베주의 정리에 의해 참이다. 주의할 점은 그 역은 성립하지 않는다.

 

$a_{1},..., a_{n}$의 최대공약수의 배수라고 하더라도, $k_{1}a_{1} + ... + k_{n}a_{n}$이 만들 수 없을 수 있다.

 

예를 들어 6원짜리 동전과 14원짜리 동전이 있을때, 이 두 수의 최대공약수는 2이다.

 

다만, 2의 배수 2,4,8,10은 만들지 못한다.

 

하지만, 6,14,20,... 등등 만들 수 있는 수는 2의 배수이다.

 

최대공약수가 1이 아니라면, $k_{1}a_{1} + ... + k_{n}a_{n}$이 만들 수 없는 수는 무한히 존재한다.

 

예를 들어 6원짜리 동전과 14원짜리 동전으로 홀수는 절대로 만들 수 없다.

 

다만, 최대공약수가 1이라면, 슈어의 정리(Schur's theorem)에 의해 만들 수 없는 수들의 집합이 유한하여, 프로베니우스의 수가 존재한다.

 

 

4. 슈어의 정리(Schur's theorem)

 

서로소인 정수 집합 $a_{1},a_{2},..., a_{n}$에 대해, $x= c_{1}a_{1} + c_{2}a_{2} + ... + c_{n}a_{n}$을 만족하는

 

음이 아닌 정수 조합 $c_{1},c_{2},...,c_{n}$의 서로 다른 개수는 x가 커질수록

 

 

 

에 수렴한다.

 

이 정리의 결과는, 서로소인 정수 집합 $a_{1},...,a_{n}$이 주어질때, 이들의 음이 아닌 정수들의 선형결합

 

$c_{1}a_{1} + c_{2}a_{2} + ... + c_{n}a_{n} = x$이 존재하여,

 

이보다 더 큰 수는 $a_{1},...a_{n}$의 선형결합으로 만들 수 있는 방법이 최소 1가지 이상 존재한다.

 

따라서 a에 1이 없다면, 어떤 상한이 반드시 존재하므로, 그 이상의 수는 무조건 만들 수 있다는 뜻이다.

 

 

5. 슈어의 상한(Schur's bound)

 

대략적인 상한을 어떻게 구할까

 

여러가지가 있긴함

 

1) $a_{1},a_{2},...,a_{n}$에서 min값과 max값에 대하여, 프로베니우스의 수 g(a_{1},...a_{n})의 상한은

 

 

 

2) n개의 동전의 max값에 대하여, 프로베니우스의 수의 상한은...

 

 

 

3) n개의 동전에 대하여..

 

 

 

 

 

 

 

6. 예시 문제

 

https://www.acmicpc.net/problem/35293

 

+9, +7, +4.5, -2를 가지고 정확히 n을 만들기 위해 각각 사용하는 횟수들의 합은 얼마인가?

 

여기서 n의 최댓값이 $10^{16}$이다.

 

n이 매우 크기 때문에, n을 어떤 방법으로든 줄이는게 해법임은 쉽게 눈치챌 수 있는데.. 어떻게 줄일 수 있을까?

 

먼저 n이 소수점 한자리까지만 주어지는데, n이 매우 크다면(10^15이상), float(input())으로 받더라도, 정수로 처리해버린다고 한다.

 

그래서 소수점 한자리까지만 주어진다는 점을 이용해서 input()으로 받은 다음, .을 기준으로 정수부분과 소수부분을 나눠야한다.

 

n = input()

f = n[-1]
m = n[:-2]

 

 

 

4.5만 사용할 수 있기 때문에 주어진 값이 5.0, 7.5같이 ~.0이나 ~.5가 아니면 절대로 불가능하다.

 

n = input()

f = n[-1]
m = n[:-2]

if f == 0 or f == 5:

else:
    
    print(-1)

 

 

4.5를 다루기는 까다롭기 때문에, 각각의 수를 2배한다.

 

즉, 9,4.5,7,-2를 2배하여 18,14,9,-4를 사용한다고 가정한다.

 

당연히 n도 2배를 해야한다.

 

n = input()

f = int(n[-1])
m = int(n[:-2])

if f == 0 or f == 5:
    
    m *= 2
    
    if f == 5:
        
        m += 1
        
else:
    
    print(-1)

 

 

이제 18원, 14원, 9원, -4원을 사용하여 n원을 만드는 방법에 대해 생각해보자.

 

이 문제는 18x + 14y + 9z -4w = n을 만족하는 x+y+z+w의 최솟값을 구하는 문제와 같다.

 

n이 적당히 작다면, BFS를 이용해서 쉽게 구할 수 있다.

 

다만, n이 매우 크다면 어떨까?

 

먼저 18을 사용하지 않는다고 가정해보자. 즉, 14,9,-4만으로 매우 큰 n을 만들 수 있을까?

 

+9를 2번 선택하면, +18을 1번 선택하는 것과 마찬가지이므로, x+y+z+w의 최솟값을 구하기 위해서는

 

+9를 2번 선택하는 것보다 +18을 1번 선택하는 것이 유리하다.

 

마찬가지로 +14를 9번 쓰는 것보다 +18을 7번 쓰는 것이 유리하다. 따라서, 18은 사용하는 것이 무조건 유리하다.

 

그렇다면, 18,14,9,-4를 사용한다고 생각해보자.

 

하지만, 18 1번, -4 1번을 사용하는 것보다 14 1번을 사용하는 것이 무조건 유리하다.

 

그러므로, 적당히 큰 n에 대해서는 -4는 사용할 필요가 없다. 왜냐하면 18을 무조건 써야하는데, -4까지 써야한다면 그것은 14로 대체되기 때문이다.

 

따라서, 매우 큰 n에 대해서는 18,14,9를 사용하여 n을 만드는 문제와 같다.

 

그런데, 18,14,9의 최대공약수는 1이므로, 18,14,9에 대한 프로베니우스의 수가 존재한다.

 

즉, 프로베니우스의 수보다 큰 수는 18,14,9로 무조건 만들 수 있다.

 

그러므로, n이 매우 크다면, (18x+14y+9z) + (18a+14b+9c-4w) = n으로 분해해서 생각할 수 있다.

 

여기서 (18x+14y+9z)는 매우 큰 수이고, (18a+14b+9c-4w)는 적당한 프로베니우스의 수 이하의 수이다.

 

그러면 어떻게 분해하는게 유리할까?

 

매우 큰 수 (18x+14y+9z)는 y = 0, z = 0이고 x만을 사용하는게 유리하다.

 

즉, 매우 큰 n에 대해서 일단 18을 사용해서 최대한 줄이고, 적당히 작은 수로 만든 다음, 그 수에 대해서는 18a+14b+9c-4w로

 

BFS를 이용해 a+b+c+w의 최솟값을 구하는 것이다.

 

여기서 문제는 18을 사용해서 최대한 줄일때, 어디까지 줄이냐이다.

 

슈어의 상한을 이용해서 18*9 - 18 - 9 = 162-27 = 135정도인데, 적당히 안전하게 n이 200이하에 대해서는 BFS로 가능한 모든 경우를 구해 DP배열에 저장해두고,

 

N이 매우 큰 경우, 일단 18만 사용해서 N을 200근처로 떨어뜨린 다음, 미리 구해둔 DP배열의 수를 사용해서 그 수와 더하면 된다

 

from collections import deque

n = input()

f = int(n[-1])
m = int(n[:-2])

if f == 0 or f == 5:
    
    m *= 2

    if f == 5:
        
        m += 1
    
    INF = 10**12
    dp = [INF]*201
    dp[0] = 0
    dp[18] = 1
    dp[9] = 1
    dp[14] = 1

    queue = deque([18,14,9])

    while queue:
        
        u = queue.popleft()

        for a in [18,14,9,-4]:
            
            du = u + a

            if du >= 0 and du <= 200:
                
                if dp[du] > dp[u]+1:
                    
                    dp[du] = dp[u]+1
                    queue.append(du)
    
    count = 0
    
    if m > 200:
        
        count += (m-183)//18

        m -= count*18

    print(count + dp[m])

else:
    
    print(-1)

 

 

어떤 수 m을 200 근방으로 떨어뜨리는 스킬은 (m-183)//18이다.

 

(m-x)//d하면 m을 x~x+(d-1)사이로 만들 수 있다.

 

왜냐하면, m-x = dq + r이다.

 

이떄, 남은 숫자는 m - dq이므로, m-dq = x+r이다.

 

r는 0~d-1이므로, 남은 숫자 m-dq는 x~x+(d-1)까지이다.