백준 2169번 - 로봇 조종하기

문제

백준 2169번 - 로봇 조종하기

---

아이디어

오른쪽과 아래로만 움직일 수 있으면 간단한 DP 식으로 해결할 수 있지만 이 문제에서는 왼쪽으로도 움직일 수 있다는 조건이 있다. 왼쪽 이동까지 고려한 DP로 해결해야 한다.

1. 가치 배열 초기화

int[][] arr = new int[n + 1][m + 1];

for (int i = 1; i <= n; i++) {
    st = new StringTokenizer(br.readLine());
    for (int j = 1; j <= m; j++) {
        arr[i][j] = Integer.parseInt(st.nextToken());
    }
}

2. dp 배열 초기화

int[][] dp = new int[n + 1][m + 1];

//첫번째 행 처리
for (int i = 1; i <= m; i++) {
    dp[1][i] = dp[1][i - 1] + arr[1][i];
}

• dp[i][j]는 (i, j) 에서 얻는 최댓값이다.
• 처음 첫 행은 오른쪽으로만 이동 가능하다. 누적합을 구하듯이 초깃값 설정이 가능하다.

3. dp 배열 채우고 결과 출력

//0 = 왼쪽에서 오른쪽
//1 = 오른쪽에서 왼쪽
int[][] temp = new int[2][m + 2];

//2번째 행 ~ N번째 행
for (int i = 2; i <= n; i++) {

    //왼쪽에서 오른쪽 ->
    temp[0][0] = Integer.MIN_VALUE;
    for (int j = 1; j <= m; j++) {
        temp[0][j] = Math.max(temp[0][j - 1], dp[i - 1][j]) + arr[i][j];
    }
    
    //오른쪽에서 왼쪽 <-
    temp[1][m + 1] = Integer.MIN_VALUE;
    for (int j = m; j >= 1; j--) {
        temp[1][j] = Math.max(temp[1][j + 1], dp[i - 1][j]) + arr[i][j];
    }
    
    //두 가지 방향 중 최댓값
    for (int j = 1; j <= m; j++) {
        dp[i][j] = Math.max(temp[0][j], temp[1][j]);
    }
}

System.out.println(dp[n][m]);

• temp 배열은 dp 배열을 채우는데 사용할 보조 배열이다. 0행은 오른쪽 이동, 1행은 왼쪽 이동했을 때 최댓값을 저장한다.
• 첫번째 행은 위에서 초깃값으로 설정했으므로 2번째 행부터 N번째 행까지 구한다.
• 왼쪽에서 오른쪽 방향 점화식 => temp[0][j] = max(왼쪽에서 온 경우, 위쪽에서 온 경우) + 현재 점수
• 오른쪽에서 왼쪽 방향 점화식 => temp[1][j] = max(오른쪽에서 온 경우, 위쪽에서 온 경우) + 현재 점수
• dp[i][j]에는 두 방향 중 최댓값을 저장한다.

---

예상 시간 복잡도

• 예상 시간 복잡도 : O(NM)

---

코드 구현 - 자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ_2169 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] arr = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][] dp = new int[n + 1][m + 1];

        //첫번째 행 처리
        for (int i = 1; i <= m; i++) {
            dp[1][i] = dp[1][i - 1] + arr[1][i];
        }

        //0 = 왼쪽에서 오른쪽
        //1 = 오른쪽에서 왼쪽
        int[][] temp = new int[2][m + 2];

        //2번째 행 ~ N번째 행
        for (int i = 2; i <= n; i++) {

            //왼쪽에서 오른쪽 ->
            temp[0][0] = Integer.MIN_VALUE;
            for (int j = 1; j <= m; j++) {
                temp[0][j] = Math.max(temp[0][j - 1], dp[i - 1][j]) + arr[i][j];
            }

            //오른쪽에서 왼쪽 <-
            temp[1][m + 1] = Integer.MIN_VALUE;
            for (int j = m; j >= 1; j--) {
                temp[1][j] = Math.max(temp[1][j + 1], dp[i - 1][j]) + arr[i][j];
            }

            //두 가지 방향 중 최댓값
            for (int j = 1; j <= m; j++) {
                dp[i][j] = Math.max(temp[0][j], temp[1][j]);
            }
        }

        System.out.println(dp[n][m]);
    }
}

코드 구현 - 파이썬

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [[0] * (m + 1) for _ in range(n + 1)]
dp = [[0] * (m + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    data = input().split()
    for j in range(1, m + 1):
        arr[i][j] = int(data[j - 1])

for i in range(1, m + 1):
    dp[1][i] = dp[1][i - 1] + arr[1][i]

temp = [[0] * (m + 2) for _ in range(2)]

for i in range(2, n + 1):

    temp[0][0] = float('-inf')
    for j in range(1, m + 1):
        temp[0][j] = max(temp[0][j - 1], dp[i - 1][j]) + arr[i][j]

    temp[1][m + 1] = float('-inf')
    for j in range(m, 0, -1):
        temp[1][j] = max(temp[1][j + 1], dp[i - 1][j]) + arr[i][j]

    for j in range(1, m + 1):
        dp[i][j] = max(temp[0][j], temp[1][j])

print(dp[n][m])