[알고리즘] 백준 - 로봇 조종하기

백준 - 로봇 조종하기

다른 사람 풀이

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

public class Main {

    static int N;
    static long[][] dp;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int i, j, n = sc.nextInt(), m = sc.nextInt();
        int[][] map = new int[n + 1][m + 1];
        int d[][] = new int[n + 1][m + 1];
        int tmp[][] = new int[2][m + 2];

        for (i = 1; i <= n; i++) {
            for (j = 1; j <= m; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        sc.close();

        d[1][1] = map[1][1];
        for (i = 2; i <= m; i++) {
            d[1][i] = d[1][i - 1] + map[1][i];
        }

        for (i = 2; i <= n; i++) {
            tmp[0][0] = d[i-1][1];
            for (j = 1; j <= m; j++) {
                tmp[0][j] = Math.max(tmp[0][j - 1], d[i - 1][j]) + map[i][j];
            }
            tmp[1][m + 1] = d[i - 1][m];
            for (j = m; j >= 1; j--) {
                tmp[1][j] = Math.max(tmp[1][j + 1], d[i - 1][j]) + map[i][j];
            }

            for (j = 1; j <= m; j++) {
                d[i][j] = Math.max(tmp[0][j], tmp[1][j]);
            }
        }
        System.out.println(d[n][m]);
    }
}

로봇이 왼쪽, 오른쪽, 아래쪽으로 움직일 수 있으니 이전 위치는 현재 위치의 오른쪽, 왼쪽, 위쪽이라는 뜻이 된다. 그 중에서 max 값을 찾으면된다. 하지만 일반적인 이중 for문으로 풀게되면 오른쪽에서 오는 것을 잘 반영할 수 없다. 따라서 tmp배열에 오른쪽에서 왔는지, 왼쪽에서 왔는지 구분하여 저장하고 나중에 최대값을 찾아줘야한다.

참고 블로그
https://heedipro.tistory.com/263

참고 블로그2 (설명 자세)
https://blog.naver.com/occidere/220808155184