99클럽 코테 스터디 25일차 TIL (챌린저): [백준][Java] 2169 로봇 조종하기 - 골드2

 

문제 보기

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

 

 

풀이

이동은 아래, 왼쪽, 오른쪽으로 밖에 못 한다.

칸을 재방문하는 것이 불가능하지만 왼쪽은 이전에도 왼쪽에서, 오른쪽은 이전에도 오른쪽에서 온 것이라면 상관없다.

 

처음엔 3차원 배열을 사용해 어느 방향으로 이동했는지를 기록했는데 한 for문 안에서 다 처리하려니 오른쪽에서 왼쪽으로 탐색하는 경우가 기록이 되지 않았다.

 

순서를 어떻게 하면 좋을지 생각하다가 그냥 한 줄씩 왼쪽 이동, 오른쪽 이동 최댓값을 따로 구하고 그중에서 최댓값을 한 번 더 구하는 방식을 채택했다.

 

int[][] dp = new int[N][M];
dp[0][0] = matrix[0][0];
for(int i = 1; i < M; i++) {
  dp[0][i] = dp[0][i-1] + matrix[0][i];
}

for(int i = 1; i < N; i++) {
  int[][] temp = new int[2][M];
  temp[0][0] = dp[i-1][0] + matrix[i][0];
  for(int j = 1; j < M; j++) {
    temp[0][j] = Math.max(dp[i - 1][j], temp[0][j - 1]) + matrix[i][j];
  }
  temp[1][M-1] = dp[i-1][M-1] + matrix[i][M-1];
  for(int j = M - 2; j >= 0; j--) {
    temp[1][j] = Math.max(dp[i - 1][j], temp[1][j + 1]) + matrix[i][j];
  }
  for(int j = 0; j < M; j++) {
    dp[i][j] = Math.max(temp[0][j], temp[1][j]);
  }
}

첫 줄은 왼쪽에서 오른쪽으로 이동하는 경우의 수밖에 없기 때문에 따로 계산했다.

오른쪽으로 이동에서 x값이 0일 때,

왼쪽으로 이동해서 x값이 M-1일 때도 마찬가지다.

 

 

전체 코드

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

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

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

    int[][] dp = new int[N][M];
    dp[0][0] = matrix[0][0];
    for(int i = 1; i < M; i++) {
      dp[0][i] = dp[0][i-1] + matrix[0][i];
    }

    for(int i = 1; i < N; i++) {
      int[][] temp = new int[2][M];
      temp[0][0] = dp[i-1][0] + matrix[i][0];
      for(int j = 1; j < M; j++) {
        temp[0][j] = Math.max(dp[i - 1][j], temp[0][j - 1]) + matrix[i][j];
      }
      temp[1][M-1] = dp[i-1][M-1] + matrix[i][M-1];
      for(int j = M - 2; j >= 0; j--) {
        temp[1][j] = Math.max(dp[i - 1][j], temp[1][j + 1]) + matrix[i][j];
      }
      for(int j = 0; j < M; j++) {
        dp[i][j] = Math.max(temp[0][j], temp[1][j]);
      }
    }

    bw.write(dp[N-1][M-1] + "");


    bw.flush();
    bw.close();
  }

}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Gold/2169.%E2%80%85%EB%A1%9C%EB%B4%87%E2%80%85%EC%A1%B0%EC%A2%85%ED%95%98%EA%B8%B0

CodingTest_AutoSave/백준/Gold/2169. 로봇 조종하기 at main · MetroDefro/CodingTest_AutoSave