Q2169. 로봇 조종하기

최대값을 저장하며 나아가는 로직

문제는 로봇이 왼쪽, 오른쪽, 아래쪽으로 갈 수 있습니다.

따라서 아래쪽으로 이동할경우를 고려하여 오른쪽 방향으로 이동할 경우의 최대값과 왼쪽 방향으로 이동할 경우의 최대값을 구해야합니다.

첫째줄은 max값 비교없이 오른쪽으로 이동하면 됩니다.

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q2169 { static int[][] dp, value; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int y = Integer.parseInt(st.nextToken()); int x = Integer.parseInt(st.nextToken()); dp = new int[y+1][x+1]; value = new int[y+1][x+1]; for (int i = 1; i <= y; i++) { st = new StringTokenizer(br.readLine()); for (int j = 1; j <= x; j++) { value[i][j] = Integer.parseInt(st.nextToken()); } } int[] moveRight = new int[x+1]; dp[1][1] = value[1][1]; for (int j = 2; j <= x; j++) { dp[1][j] = dp[1][j-1] + value[1][j]; } for (int i = 2; i <= y; i++) { moveRight = new int[x+1]; moveRight[1] = dp[i-1][1] + value[i][1]; for (int j = 2; j <= x; j++) { moveRight[j] = Math.max(moveRight[j-1], dp[i-1][j]) + value[i][j]; } int[] moveLeft = new int[x+1]; moveLeft[x] = dp[i-1][x] + value[i][x]; for (int j = x-1; j >= 1; j--) { moveLeft[j] = Math.max(dp[i-1][j], moveLeft[j+1]) + value[i][j]; } for (int j = 1; j <= x; j++) { dp[i][j] = Math.max(moveLeft[j], moveRight[j]); } } System.out.println(dp[y][x]); } }