[백준 2169] 로봇 조종하기 (C#, C++) - soo:bak

문제 링크

2169번 - 로봇 조종하기

설명

N × M 크기의 화성 지도가 주어지는 상황에서, N과 M (1 ≤ N, M ≤ 1,000)과 각 칸의 탐사 가치가 주어질 때, (1, 1)에서 시작하여 (N, M)까지 이동하면서 얻을 수 있는 최대 가치를 구하는 문제입니다.

로봇은 좌, 우, 아래로만 이동할 수 있으며 위로는 이동할 수 없습니다. 또한 한 번 방문한 칸은 다시 방문할 수 없습니다. 각 칸의 가치는 -100부터 100 사이의 정수입니다.

접근법

동적 프로그래밍으로 각 위치까지 도달할 수 있는 최대 가치를 계산합니다. dp[r][c]를 (r, c) 위치까지 이동했을 때의 최대 가치로 정의합니다.

첫 번째 행은 오른쪽으로만 이동할 수 있으므로 왼쪽부터 차례대로 가치를 누적합니다.

두 번째 행부터는 위에서 내려오는 경로와 좌우로 이동하는 경로를 모두 고려해야 합니다.

이를 위해 각 행에 대해 두 번 순회합니다.

첫 번째 순회는 왼쪽부터 오른쪽으로 진행하며, 각 위치에서 위에서 내려온 값과 왼쪽에서 온 값 중 큰 값을 선택합니다.

두 번째 순회는 오른쪽부터 왼쪽으로 진행하며, 위에서 내려온 값과 오른쪽에서 온 값 중 큰 값을 선택합니다.

각 위치의 최종 값은 좌→우 순회 결과와 우→좌 순회 결과 중 큰 값으로 결정됩니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var input = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      var n = input[0];
      var m = input[1];
      
      var value = new int[n + 1, m + 1];
      for (var r = 1; r <= n; r++) {
        var line = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
        for (var c = 1; c <= m; c++)
          value[r, c] = line[c - 1];
      }

      var dp = new int[n + 1, m + 1];
      for (var c = 1; c <= m; c++)
        dp[1, c] = dp[1, c - 1] + value[1, c];

      for (var r = 2; r <= n; r++) {
        var left = new int[m + 1];
        var right = new int[m + 2];

        left[1] = dp[r - 1, 1] + value[r, 1];
        for (var c = 2; c <= m; c++)
          left[c] = Math.Max(dp[r - 1, c], left[c - 1]) + value[r, c];

        right[m] = dp[r - 1, m] + value[r, m];
        for (var c = m - 1; c >= 1; c--)
          right[c] = Math.Max(dp[r - 1, c], right[c + 1]) + value[r, c];

        for (var c = 1; c <= m; c++)
          dp[r, c] = Math.Max(left[c], right[c]);
      }

      Console.WriteLine(dp[n, m]);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;
  
  vvi value(n + 1, vi(m + 1));
  for (int r = 1; r <= n; r++)
    for (int c = 1; c <= m; c++)
      cin >> value[r][c];

  vvi dp(n + 1, vi(m + 1, 0));
  for (int c = 1; c <= m; c++)
    dp[1][c] = dp[1][c - 1] + value[1][c];

  for (int r = 2; r <= n; r++) {
    vi left(m + 1, 0);
    vi right(m + 2, 0);
    
    left[1] = dp[r - 1][1] + value[r][1];
    for (int c = 2; c <= m; c++)
      left[c] = max(dp[r - 1][c], left[c - 1]) + value[r][c];

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

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

  cout << dp[n][m] << "\n";
  
  return 0;
}