[Python] 32518번 대충 블록에서 영혼 탈출시키는 게임

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

---

 

24/11/08

 

 

간단한 탑다운 DP다. 바텀업으로는 해결할 수 없다.

---

 

문제 접근 방식:

 

 

처음에는 $N$의 제한이 $10^{18}$인 것을 보고 DP가 아니라 하나의 완성된 수식으로 나올 줄 알고 100까지의 바텀업 DP를 돌렸다.

 

뚜렷한 규칙이 보이지 않아서, 수학적으로 해결하는 것은 그만두고, 다른 해결방법이 있는지 모색하기 위해 어떤 경우에 최댓값이 나오고, 그때 분할되는 경우가 어떤 경우인지를 모두 찾는 코드를 작성했다.

 

$N-2$가 3으로 나눠진다면, $((N-2)//3, (N-2)//3, (N-2)//3)$과 같이 분할된다.

 

예를 들어, 8과 같은 경우, 들어내는 블록을 기준으로 3개의 체인이 나오는데, 각 체인의 길이는 $(2, 2, 2)$가 나온다.

 

$N-2$를 3으로 나눈 나머지가 1이라면, $((N-2)//3, (N-2)//3 + 1, (N-2)//3)$과 같이 분할된다.

 

예를 들어, 9와 같은 경우, 들어내는 블록을 기준으로 3개의 체인이 나오고, 각 체인의 길이는 $(2, 3, 2)$가 나온다.

 

$N-2$를 3으로 나눈 나머지가 2라면, $((N-2)//3, (N-2)//3 + 1, (N-2)//3 + 1)$, 혹은, $((N-2)//3, (N-2)//3, (N-3)//3 + 2)$와 같이 분할된다.

 

예를 들어, 10과 같은 경우, 들어내는 블록을 기준으로 3개의 체인이 나오고, 각 체인의 길이는 $(2, 3, 3)$ 혹은 $(2, 2, 4)$가 나온다.

 

따라서, 이를 토대로 탑다운 DP를 수행하면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 32518번 대충 블록에서 영혼 탈출시키는 게임
# DP
'''
접근 방법:
[0, 0, 0, 1, 1, 2]...
DP를 통해 규칙을 찾아보자.
복잡하니까 탑다운 DP
'''
'''
DP = [0, 0, 0, 1, 1, 2]
for i in range(6, 101):
    M = 0
    ok = []
    for p in range(1, i-3):
        for q in range(1, i-p-2):
            r = i-p-q-2
            A = min(p, q, r)
            if A > M:
                ok = []
                ok.append((p, q, r))
                M = A
            elif A == M:
                ok.append((p, q, r))
    print(i, ok)
    DP.append(max(2+DP[t]+DP[u]+DP[v] for t, u, v in ok))
#print(*DP)
'''
DP = dict()
L = [0, 0, 0, 1, 1, 2]
for i in range(6):
    DP[i] = L[i]
def dfs(n):
    if n in DP:
        return DP[n]
    if (n-2) % 3 == 0:
        if (n-2)//3 not in DP:
            DP[(n-2)//3] = dfs((n-2)//3)
        return 2+3*DP[(n-2)//3]
    elif (n-2) % 3 == 1:
        if (n-2)//3 not in DP:
            DP[(n-2)//3] = dfs((n-2)//3)
        if (n-2)//3 + 1 not in DP:
            DP[(n-2)//3+1] = dfs((n-2)//3+1)
        return 2+2*DP[(n-2)//3]+DP[(n-2)//3+1] 
    else:
        if (n-2)//3 not in DP:
            DP[(n-2)//3] = dfs((n-2)//3)
        if (n-2)//3 + 1 not in DP:
            DP[(n-2)//3+1] = dfs((n-2)//3+1)
        if (n-2)//3 + 2 not in DP:
            DP[(n-2)//3+2] = dfs((n-2)//3+2)
        return max(2+DP[(n-2)//3]+2*DP[(n-2)//3+1], 2+2*DP[(n-2)//3]+DP[(n-2)//3+2])
print(dfs(int(input())))