[Code Jam 2021 Round 2] Matrygons 풀이

N개의 side를 채우기 위해 작은 Polygon부터 생각해보면 polygon의 side 개수는 배수로 증가한다.

예를 들어, 33 = 3(1+10) 혹은 11(1+2)와 같이 나타낼 수 있다. 재귀적으로 3(1+10)은 또 3(1+2(1+4))와 같이 나타낼 수 있다.

f(p)를 다음과 같이 정의하자.

f(p) : p를 만들기 위해 2보다 크거나 같은 p의 약수 qi를 사용해서 p=q0+q0q1+q0q1q2+...+q0q1...qn으로 나타낼 때 최대 항의 수

말이 좀 어려운데, 예를 들어보면 22=2(1+10)=2(1+2(1+4))이므로 f(22)=3이다.

g(p) : p를 만들기 위해 3보다 크거나 같은 p의 약수 qi를 사용해서 p=q0+q0q1+q0q1q2+...+q0q1...qn으로 나타낼 때 최대 항의 수

 

 

$$ f(p)=1+max_{{2{\leq}q<p}, {q|p}}f(p/q-1) $$

$$ g(p)=1+max_{{3{\leq}q<p}, {q|p}}f(p/q-1) $$

 

 

g(N)을 구하면 답이 된다. 왜냐하면 최소 polygon의 side 개수는 3이고 3으로 묶은 다음 그 다음부터는 2 이상인 약수로 최대한 많은 항의 수로 묶는 것이 답이 되기 때문이다.

Python 코드는 다음과 같다.

MAX = 1000000

T = int(input())
N = []
for x in range(1, T + 1):
    N.append(int(input()))

divisors = [[] for _ in range(MAX + 1)]
for d in range(2, MAX + 1):
    for n in range(2 * d, MAX + 1, d):
        divisors[n].append(d)

f = [0] * (MAX + 1)
f[2] = 1
g = [0] * (MAX + 1)
for n in range(3, MAX + 1):
    max_f, max_g = 1, 1
    for q in divisors[n]:
        max_f = max(max_f, f[n//q-1]+1)
        if q > 2:
            max_g = max(max_g, f[n//q-1]+1)
    f[n] = max_f
    g[n] = max_g

for x in range(1, T + 1):
    print(f'Case #{x}: {g[N[x-1]]}')