[Algorithm] 🤖백준 2169 로봇 조종하기

0. 문제

NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만, 로봇의 메모리가 얼마 안 되기 때문에 지형을 N×M 배열로 단순화 하여 생각하기로 한다.

지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다. 또한 한 번 탐사한 지역(배열에서 하나의 칸)은 탐사하지 않기로 한다.

각각의 지역은 탐사 가치가 있는데, 로봇을 배열의 왼쪽 위 (1, 1)에서 출발시켜 오른쪽 아래 (N, M)으로 보내려고 한다. 이때, 위의 조건을 만족하면서, 탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오.

입력
첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다.

출력
첫째 줄에 최대 가치의 합을 출력한다.

1. 아이디어

2가지 경우 모두 탐색
1) 왼쪽 → 오른쪽 방향으로 진행 (left)
2) 오른쪽 → 왼쪽 방향으로 진행 (right)
두 개의 결과값 중 더 큰 값 dp에 저장

2. 핵심 풀이

2가지 경우 모두 탐색
1) 왼쪽 → 오른쪽 방향으로 진행 (left)

left[1] = dp[r-1][1] + map[r][1];
for(int c=2; c<m+1; c++)
		left[c] = Math.max(left[c-1], dp[r-1][c]) + map[r][c];

2) 오른쪽 → 왼쪽 방향으로 진행 (right)

right[m] = dp[r-1][m] + map[r][m];
for(int c=m-1; c>=1; c--)
		right[c] = Math.max(right[c+1], dp[r-1][c]) + map[r][c];

두 개의 결과값 중 더 큰 값 dp에 저장

for(int c=1; c<m+1; c++)
				dp[r][c] = Math.max(left[c], right[c]);

3. 코드

import java.io.*;

public class DP_9 {
	static int map[][], dp[][], left[], right[];
	static int n, m;
	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s[] = br.readLine().split(" ");
		n = Integer.parseInt(s[0]);
		m = Integer.parseInt(s[1]);
		
		map = new int[n+1][m+1];
		dp = new int[n+1][m+1];
		left = new int[m+1];
		right = new int[m+1];
		
		for(int i=1; i<n+1; i++) {
			s = br.readLine().split(" ");
			for(int j=1; j<m+1; j++) {
				map[i][j] = Integer.parseInt(s[j-1]);
			}
		}
		
		for(int i=1; i<m+1; i++)
			dp[1][i] = (dp[1][i-1] + map[1][i]);
		
		System.out.println(control());
	}
	
	static int control() {
		
		for(int r=2; r<n+1; r++) {
			left[1] = dp[r-1][1] + map[r][1];
			for(int c=2; c<m+1; c++)
				left[c] = Math.max(left[c-1], dp[r-1][c]) + map[r][c];
			
			right[m] = dp[r-1][m] + map[r][m];
			for(int c=m-1; c>=1; c--)
				right[c] = Math.max(right[c+1], dp[r-1][c]) + map[r][c];
			
			for(int c=1; c<m+1; c++)
				dp[r][c] = Math.max(left[c], right[c]);
			
		}
		
		return dp[n][m];
	}
}

4. 결과

성공~