[BOJ] 2169 - 로봇 조종하기 (Python)

 

 

아이디어

 

위쪽, 왼쪽, 오른쪽의 가능한 지역 중 최대 가치를 더해 나간다.

 

 

풀이

 

입력 받은 N, M을 저장하고, 첫 행을 입력 받아 리스트 dp에 저장한다.

첫 행의 지역들은 시작 지점을 제외하고는 왼쪽 지역을 탐사해야 이동할 수 있으므로, dp를 오른쪽으로 누적하여 더한다.

 

첫 행과 마지막 행의 지역들을 제외한 지역들을 처리하기 위해 N-2의 크기로 for문을 실행한다(N > 2일 때 실행).

우선 현재 행을 arr에 입력 받고, arr과 같은 크기로 0이 채워진 리스트 temp를 생성한다.

 

temp에는 왼쪽에서 오른쪽으로 탐사해 나갈 때의 최대 가치를 저장한다.

temp의 첫 번째 값은 arr의 첫 번째 값(현재 지역 가치)과 dp의 첫 번째 값(위쪽 지역 최대 누적 가치)의 합으로 저장하고,

나머지 값들은 왼쪽 지역(temp)과 위쪽 지역(dp)의 최대 누적 가치 중 더 큰 값과 현재 지역 가치(arr)를 더해 나간다.

 

이번에는 오른쪽에서 왼쪽으로 탐사해 나갈 때의 최대 가치를 arr에 저장한다.

arr의 마지막 값에 dp의 마지막 값(위쪽 지역 최대 누적 가치)를 더하고,

나머지 값들은 오른쪽 지역(arr)과 위쪽 지역(dp)의 최대 누적 가치 중 더 큰 값을 더해 나간다.

 

마지막으로 temp와 arr의 값들을 서로 비교해 더 큰 값을 arr에 저장하고 dp에 arr을 할당한다.

 

N이 1일 때는 첫 for문에서 구한 dp의 마지막 값이 결과값이 되므로 마지막 행은 N > 1일 때 계산한다.

마지막 행은 왼쪽 방향으로 탐사가 불가능하므로 오른쪽 방향으로 최대 누적 가치를 더해 나가고, 결과값을 출력한다.

 

import sys

input = sys.stdin.readline

def solution():
    N, M = map(int, input().split())
    dp = list(map(int, input().split()))
    for i in range(M-1):
        dp[i+1] += dp[i]
    for _ in range(N-2):
        arr = list(map(int, input().split()))
        temp = [0]*M
        temp[0] = arr[0]+dp[0]
        for i in range(1, M):
            temp[i] = arr[i]+max(dp[i], temp[i-1])
        arr[-1] += dp[-1]
        for i in range(M-2, -1, -1):
            arr[i] += max(dp[i], arr[i+1])
        for i in range(M):
            arr[i] = max(arr[i], temp[i])
        dp = arr
    if N > 1:
        arr = list(map(int, input().split()))
        arr[0] += dp[0]
        for i in range(1, M):
            arr[i] += max(dp[i], arr[i-1])
        dp = arr
    print(dp[-1])

solution()

 

 

한 행씩 입력 받아 처리할 수 있으므로 한번에 모든 행을 입력 받아 저장하지 않아도 된다.

# 메모리가 더 많이 사용되는 코드
N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

 

함수를 사용하지 않은 코드보다 함수를 정의하여 함수 내부에서 동작하도록 한 코드가 더 빨랐다.

# 1.
import sys

input = sys.stdin.readline

N, M = map(int, input().split())
dp = list(map(int, input().split()))
...

# 2. 더 빠른 코드
import sys

input = sys.stdin.readline

def solution():
    N, M = map(int, input().split())
    dp = list(map(int, input().split()))
...