[백준-파이썬] 14550: 마리오 파티

문제 보러 가기!

DP문제 !!

입력이 특이한 것 같다..- 여러 줄에 걸쳐서 N개의 정수가 주어지는 부분, 테스트케이스가 몇 개인지 안 알려주고 맨 끝에 0이 오는 부분.
try, except를 이용해서 편하게 테스트케이스 수만큼 동작하게 했다.
여러 줄에 걸쳐서 N개 정수가 주어지는 부분을 위해서, 리스트로 받고 개수를 세다가 N개가 되면 그만 받게 했다.

dp table을 2차원으로 만들었다.
세로: 몇 번째 이동한 것인지
가로: 해당 위치
값: 최대로 얻는 수익!! (예- 1번째로 이동해서 1번째 칸에 도달했을 때 얻는 최대 수익)

세로 첫 줄은 채우고 시작한다. (1~S만큼 이동할 수 있으니까 그만큼만 채우기)

그 다음 세로 줄들을 돌면서, 가로를 채운다. 

이런 식으로 된다..! 그 가로까지 올 수 있는 (세로는 해당 위치에서 -1, 가로는 1~S을 뺀 값.) 칸 중 최댓값과 그 위치의 값을 더하면 그 위치의 값이 된다. 

 

예제 2번의 경우, 위와 같은 식으로 dp 테이블이 채워진다.

최대 이동 횟수(T)의 이전 때를 기준으로 본다! -> 거기에서 1번 더 이동했을 때(1~S만큼 이동 가능), N 초과가 되어야 한다.(N을 지나쳐야 별을 얻을 수 있으므로) 그러니까 세로는 최대 이동 횟수의 이전으로 두고, 가로는 -1~ -S를 보면서 그 중 최댓값을 출력하면 된다.

 

import sys

input = sys.stdin.readline

while True:
    try:
        N, S, T = map(int, input().split())
        board = []
        cnt = 0
        while cnt < N:
            tmp = list(map(int, input().split()))
            cnt += len(tmp)
            board.extend(tmp)

        dp = [[False] * (N) for _ in range(T)]
        # 초기값
        for i in range(S):
            dp[0][i] = board[i]

        for i in range(1, T - 1):
            for j in range(N):
                tmp = -987654321
                if j == 0:
                    tmp = 0
                for k in range(1, S + 1):
                    if N > j - k >= 0:
                        if dp[i - 1][j - k] == False:
                            pass

                        else:
                            tmp = max(tmp, dp[i - 1][j - k])

                dp[i][j] = tmp + board[j]

        # 마지막
        for j in range(N):
            tmp = 0
            for k in range(1, S + 1):

                if j - k < 0:
                    pass
                else:
                    tmp = max(tmp, dp[-2][j - k])

            dp[-1][j] = tmp + board[j]
            
        ans = -9987654321
        for i in range(1, S + 1):
            ans = max(ans, dp[-2][-i])
        print(ans)

    except:
        break