[BOJ] Q2169 로봇 조종하기

[BOJ] Q2169 로봇 조종하기

Question

Language: Python

Difficulty: Gold 2

일반적으로 아래, 오른쪽 방향으로 움직이는 경우의 문제가 많은데, 이 문제의 경우 특이하게 왼쪽으로 가는 방향도 추가되어 아이디어를 떠올리기가 어려웠다.

해당 문제의 풀이를 위해 왼쪽 vs 오른쪽 경우를 비교해서 더 큰 값을 초기화 시켜주면 된다.

아래의 풀이와 같이 왼쪽, 오른쪽을 따로 진행하여, 특정 좌표 점에 도달하는 가치의 합을 저장하면 탐색을 진행하면 된다.

Solution

fimport sys
def solution():
    dp=[[0] * m for _ in range(n)]

    dp[0][0]=values[0][0]

    #첫줄 처리
    for col in range(1,m):
        dp[0][col]=dp[0][col-1]+values[0][col]
    

    for row in range(1,n):
        left2right=[0]*m
        left2right[0]=dp[row-1][0]+values[row][0]

        for col in range(1,m):
            left2right[col]=max(dp[row-1][col],left2right[col-1])+values[row][col]
        
        right2left=[0]*m
        right2left[m-1]=dp[row-1][m-1]+values[row][m-1]

        for col in range(m-2,-1,-1):
            right2left[col]=max(dp[row-1][col],right2left[col+1])+values[row][col]
    

        for col in range(m):
            dp[row][col]=max(left2right[col],right2left[col])

    print(dp[-1][-1])

if __name__ == "__main__":
    n,m=map(int,input().split())
    values=[list(map(int,input().split())) for _ in range(n)]

    solution()