[BOJ 21321] 클레이 사격 게임

문제

---

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

풀이

---

문제가 조금 난해한데, 요약하자면 높은 점수의 클레이일수록 나중에 맞춰야 하고, i번째 경로의 클레이를 맞추려면 아직 맞추지 않은 1~(i-1)번째 경로의 클레이들 중 주기가 i번째 경로의 주기의 약수인 것이 없어야 한다.

남아있는 클레이들의 정보와 현재의 점수가 주어지면 부분 문제가 성립된다.

물론 N <= 16이므로 맞춰 떨어트린 클레이들의 정보는 비트마스크로 관리하면 된다.

그런데 현재의 점수를 꼭 파라미터로 사용해야 할까?

최대의 점수를 얻고 싶으므로, 남아있는 클레이가 같다면 현재까지 얻은 점수들 중 가장 큰 것을 채택하면 된다.

코드

---

import sys

n = int(sys.stdin.readline())
score = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
dp = [0] * 2 ** n


def f(mask):
    if dp[mask]:
        return dp[mask]

    res = 0
    for i in range(n):
        if not mask & (1 << i):
            t, s = score[i]
            for j in range(i):
                if (not mask & (1 << j)) and (t % score[j][0] == 0):
                    break
            else:
                res = max(res, f(mask ^ (1 << i)) + (bin(mask).count('1') + 1) * s)

    dp[mask] = res
    return res


print(f(0))