[Python 3] BOJ - 10564 "팔굽혀펴기"

 # 문제 링크

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

10564번: 팔굽혀펴기

 

 # 풀이

 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라고 생각한다. 상태 공간을 현재까지 한 팔굽혀펴기 횟수를 cnt, 현재 득점한 순간이 끝에서 부터 몇번째 순간인지를 turn이라고 할 때 얻을 수 있는 최대 점수인 dp[cnt][turn]이라고 정의하자.

<그림 1. 전체 차례가 k인 경우>

 위 그림 1은 팔굽혀펴기 갯수를 만족시키기 위해 필요한 전체 차례가 k인 경우를 나타낸 그림이다. i번째 턴에 해당하는 점수는 $a_i$이다. 이 때 전체 팔굽혀펴기의 횟수는 $k*a_1 + (k-1)a_2 + ... + a_k$임을 알 수 있다. 그런데 현재 팔굽혀펴기를 하기 위해 필요한 횟수는 몇번째 차례에 어떤 점수를 득점했는가에 따라 달라진다.

 만약 모든 차례에 같은 점수를 득점한 경우는 $\frac{k(k-1)}{2} * p$이다. 이 때 $p$는 점수 중 하나이다. 그런데 만약 최악의 경우, 즉 팔굽혀펴기 횟수가 최대이면서 p가 최소인 경우라면 필요한 횟수는 얼마나 될까? $\frac{k(k-1)}{2} = 5000$ 이므로 k는 최대 100이 됨을 알 수 있다. 

 왜 하필 마지막을 기준으로 생각을 해야할까? 처음을 기준으로 생각하면 안되는 것일까? 처음을 기준으로 생각하게 되면 그때 끝나는 정확한 차례수를 알아야 하기 때문이다. 그런데 전체 차례의 수는 어떤 선택을 하느냐에 따라 달라지기 때문에 현재 $a_i$점을 득점했다고 해도 전체 팔굽혀펴기로 갈 수 있는 차례의 수가 $k_1,k_2,...$일 수 있기 때문이다. 따라서 전체 팔굽혀펴기의 기여도에 곱해주는 $k_i$에 어떤 수를 넣어줘야 하는지 알 수 없다. 따라서 처음을 기준으로 생각하면 안된다.

 따라서, 마지막에 얻은 점수는 전체에서 $a_k$임을 고려했을 때 마지막에 점수를 얻기 전 팔굽혀펴기의 횟수는 $k*a_1 + (k-1)a_2 + ... + 2 *a_{k-1}$이다. 또한 마지막에서 두번째 얻은 점수는 전체에서 $2 * a_{k-1}$임을 고려했을 때 마지막에서 세번째 팔굽혀펴기의 횟수는 $k*a_1 + (k-1)a_2 + ... + 3 *a_{k-2}$이다. 따라서 점화식은 아래와 같다.

$$dp[cnt][turn] = max(dp[cnt][turn], dp[cnt - turn * a_i][turn + 1])$$

 

 # 코드

import sys

# 현재까지 한 팔굽혀펴기 횟수를 cnt, 현재 득점한 순간이 끝에서 부터 몇번째 순간인지를 turn이라고 할 때 
# 얻을 수 있는 최대 점수를 리턴하는 함수
def go(cnt, turn):
    # Base Case : 팔굽혀펴기 갯수를 정확히 충족하는 경우
    if cnt == 0:
        return 0
    # Memoization
    if dp[cnt][turn] != -1:
        return dp[cnt][turn]
    dp[cnt][turn] = -9876543210
    # 점화식
    for i in range(m):
        # 현재 점수의 기여도를 뺐을 때 0 이상이 되는 경우
        if cnt - turn * arr[i] >= 0:
            dp[cnt][turn] = max(dp[cnt][turn], go(cnt - turn * arr[i], turn + 1) + arr[i])
    return dp[cnt][turn]

# tc : 테스트케이스의 수
tc = int(sys.stdin.readline())
for _ in range(tc):
    # 입력부
    n, m = map(int, sys.stdin.readline().split())
    arr = list(map(int, sys.stdin.readline().split()))
    
    # 현재까지 한 팔굽혀펴기 횟수를 cnt, 현재 득점한 순간이 끝에서 부터 몇번째 순간인지를 turn이라고 할 때 
    # 얻을 수 있는 최대 점수를 저장하는 2차원 상태 공간 배열
    dp = [[-1] * 101 for _ in range(n + 1)]
    
    # ans가 음수인 경우 팔굽혀펴기를 만족할 수 없는 경우이므로 -1 출력
    ans = go(n, 1)
    print(ans if ans > 0 else -1)