[백준 2169번] 로봇 조종하기

https://www.acmicpc.net/problem/2169

 

문제 유형

• 다이나믹 프로그래밍

 

문제 난이도

• Gold 2

 

문제 분석

 

해당 문제는 DP를 활용하는 문제이다.

문제의 조건은 다음과 같다.
1. 로봇은 왼쪽, 오른쪽, 아래쪽으로만 이동할 수 있다.
2. 한 번 지나간 지역은 다시 지나지 않는다.
3. (1,1) -> (N, M)으로 이동할 때, 지역들의 가치가 최대가 되도록 출력한다.

따라서, 다음 방향중에서 가치가 최대가 되는 것을 찾아야한다.
1. 위 -> 아래
2. 왼쪽 -> 오른쪽
3. 오른쪽 -> 왼쪽

 

 

우선 첫번째 행 같은 경우, 왼쪽에서 오른쪽으로 가는 값들을 더할 때가 최대가 될 수 밖에 없다.
-> 시작점(1,1)을 기준으로 다른 방향으로 이동해서 도착시, 아래 -> 위 방향으로 이동할 수 밖에 없게 되는데, 이는 이동해야하는 방향에 위배된다.

 

다음과 같이 78 (2,1) 자리에 있는 값의 경우, 위에서 아래로 내려오는 경우밖에 없다. (오른쪽 -> 왼쪽으로 오는 경우는 제대로 갱신이 안된 상태이므로)

 

 

다음과 같이 왼쪽에서 오는 경우와 오른쪽에서 오는 경우를 각각 구해서, 그때의 가치의 최댓값으로 행마다 갱신해주면 된다.

 

갱신 결과

 

 

 

전체 코드

package _250810;

import java.io.*;
import java.util.*;

/**
 *packageName    : _250810
 * fileName       : BOJ_G2_2169_로봇조종하기
 * author         : moongi
 * date           : 8/10/25
 * description    :
 * 로봇은 왼쪽, 오른쪽, 아래쪽으로만 이동할 수 있다.
 * 한 번 지나간 지역은 다시 지나지 않는다.
 * (1,1) -> (N,M)으로 이동할 때, 지역들의 가치가 최대가 되도록 출력하시오.
 */
public class BOJ_G2_2169_로봇조종하기_2 {
    public static void main(String[] args) throws Exception {
       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[][] map = new int[N + 1][M + 1], dp = new int[N + 1][M + 1], tmp = new int[2][M + 2];

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

       dp[1][1] = map[1][1];
       for (int i = 2; i < M + 1; i++) {
          dp[1][i] = dp[1][i - 1] + map[1][i];
       }

       for (int i = 2; i < N + 1; i++) {
          tmp[0][0] = dp[i - 1][1]; // 왼쪽 첫째 값보다 앞의 값(0,0)은 위에서 내려온 값
          for (int j = 1; j < M + 1; j++) { // 왼쪽 -> 오른쪽
             // 좌 -> 우 vs 위 -> 아래 중 큰 값 비교. 위의 tmp[0][0]을 여기서 좌->우 값 구할 때 사용
             tmp[0][j] = Math.max(tmp[0][j - 1], dp[i - 1][j]) + map[i][j];
          }

          tmp[1][M + 1] = dp[i - 1][M]; // 오른쪽 첫째 값보다 뒤의 값(1, M+1)도 위에서 내려온 값
          for (int j = M; j >= 1; j--) {
             tmp[1][j] = Math.max(tmp[1][j + 1], dp[i - 1][j]) + map[i][j];
          }

          for (int j = 1; j <= M; j++) {
             dp[i][j] = Math.max(tmp[0][j], tmp[1][j]);
          }
       }

       System.out.println(dp[N][M]);


    }
}

 

 

 

참고한 블로그이다. 굉장히 잘 설명해주셔서 내가 작성한 내용이 부족하다면 참고하면 좋을 것 같다.

https://blog.naver.com/occidere/220808155184

[백준] 2196 - 로봇 조종하기