[Python] 17953번 디저트

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

17953번: 디저트

---

 

23/09/26

 

 

무난한 2차원 DP문제로, DP 테이블의 의미를 생각하면 쉽게 점화식을 세울 수 있다.

---

 

문제 접근 방식:

 

 

문제를 보면 전날에 먹었던 디저트와 같은 디저트를 먹으면 그 날에 얻을 수 있는 만족감보다 절반의 만족감만을 얻을 수 있다고 했다.

 

특정한 날에 디저트를 먹을 수 있는 선택지가 최대 $M = 10$까지의 제한이 있으므로, 즉, 최대 10개의 디저트가 선택지로 놓여있으므로, 이를 브루트포스로 하기에는 매우 큰 시간 복잡도가 소요 될 것이다.

 

따라서 DP테이블을 다음과 같이 세워보자.

 

$$DP[i][j] = i\textrm{번째 날에 }j\textrm{번째 디저트를 먹었을 때 느끼는 최대의 만족감}$$

 

문제에서는 $i$번째 날에 $j$번째 디저트를 먹었을 때 느끼는 만족감에 대한 배열을 주고 있다.

 

이를 $\textrm{dessert}[i][j]$라고 해보자.

 

DP테이블을 잘 생각해보면, 우리는 이전 날과 같은 디저트를 먹거나 같은 디저트를 먹지 않는 두 가지 선택지가 있다.

 

최댓값은 당연히 두 가지 선택지 중에서 더 큰 값을 취하는 것 일 것이다.

 

즉, 다음과 같다.

 

$$DP[i][j] = \max (\max (DP[i-1][k] \textrm{ except }j) + \textrm{dessert}[i][j] , DP[i-1][j] + \textrm{dessert}[i][j]//2)$$

 

DP테이블의 초깃값은 $\textrm{dessert}[0][j]$로 채우면 충분하다.

  

---

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

# 17953번 디저트
# DP
'''
접근 방법:
2차원 DP
DP[i][j] = i번째 날에 j번째 디저트를 먹었을 때 느끼는 최대의 만족감
dessert[i][j] = i번째 날에 j번째 디저트를 먹었을 때 느끼는 만족감
DP[i][j] = max(max(DP[i-1][k] except j) + dessert[i][j], DP[i-1][j] + dessert[i][j]//2)
'''
import sys
input = sys.stdin.readline

# 한 주기의 날짜 수, 디저트의 종류의 수
N, M = map(int, input().rstrip().split())
dessert = [list(map(int, input().rstrip().split())) for _ in range(M)]
DP = [[0 for _ in range(M)] for _ in range(N)]
for j in range(M):
    DP[0][j] = dessert[j][0]
for i in range(1, N):
    for j in range(M):
        max_val = 0
        for k in range(M):
            if k != j:
                val = DP[i-1][k] + dessert[j][i]
            else:
                val = DP[i-1][k] + dessert[j][i]//2
            if val > max_val:
                max_val = val
        DP[i][j] = max_val
print(max(DP[N-1]))