[백준 11048] 이동하기 (C++, C#) - soo:bak

문제 링크

11048번 - 이동하기

설명

미로를 따라 이동하면서 가장 많은 사탕을 먹을 수 있는 경로의 최대 합을 구하는 문제입니다.

미로는 N × M 크기의 격자이고, 출발점은 (1, 1), 도착점은 (N, M)입니다.

이동할 수 있는 방향은 아래 세 가지입니다:

• 아래쪽으로 한 칸 이동
• 오른쪽으로 한 칸 이동
• 대각선 오른아래 방향으로 한 칸 이동

각 칸에는 사탕이 놓여 있고, 이동할 때마다 해당 칸의 사탕을 모두 먹을 수 있습니다.

접근법

사탕을 가장 많이 얻으려면, 각 칸에 도달할 때까지 최대 사탕 개수를 누적해서 계산해야 합니다.

한 칸씩 이동하며 모든 경로를 직접 시뮬레이션하기는 어렵기 때문에,

동적 계획법(DP)을 이용하여 효율적으로 해결합니다.

접근 방식은 다음과 같습니다:

• (r, c) 칸까지 도달했을 때 얻을 수 있는 최대 사탕 수를 dp[r][c]라고 정의합니다.
• 해당 칸으로는 항상 세 방향에서 도달할 수 있습니다:
  • 왼쪽에서 온 경우: dp[r][c - 1]
  • 위쪽에서 온 경우: dp[r - 1][c]
  • 왼쪽 위 대각선에서 온 경우: dp[r - 1][c - 1]
• 따라서 현재 위치까지의 최대 사탕 수는 다음과 같이 계산됩니다:

\[dp[r][c] = \max(dp[r - 1][c],\ dp[r][c - 1],\ dp[r - 1][c - 1]) + \text{현재 칸의 사탕 수}\]

이 과정을 왼쪽 위에서 오른쪽 아래로 차례로 진행하면,

최종적으로 (N, M)에 도달했을 때의 dp[N][M]이 최대 사탕 수가 됩니다.

---

Code

C#

using System;
using System.Linq;

class Program {
  static void Main() {
    var input = Console.ReadLine().Split().Select(int.Parse).ToArray();
    int n = input[0], m = input[1];
    int[,] candy = new int[n + 1, m + 1];
    int[,] dp = new int[n + 1, m + 1];

    for (int i = 1; i <= n; i++) {
      var row = Console.ReadLine().Split().Select(int.Parse).ToArray();
      for (int j = 1; j <= m; j++)
        candy[i, j] = row[j - 1];
    }

    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        dp[i, j] = Math.Max(dp[i - 1, j],
                   Math.Max(dp[i, j - 1], dp[i - 1, j - 1])) + candy[i, j];
      }
    }

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

C++

#include <bits/stdc++.h>
#define MAX 1000

using namespace std;

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

  int candy[MAX + 1][MAX + 1] = {0, };
  int dp[MAX + 1][MAX + 1] = {0, };

  int col, row; cin >> col >> row;

  for (int i = 1; i <= col; i++) {
    for (int j = 1; j <= row; j++)
      cin >> candy[i][j];
  }

  for (int i = 1; i <= col; i++) {
    for (int j = 1; j <= row; j++)
      dp[i][j] = max({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + candy[i][j];
  }

  cout << dp[col][row] << "\n";

  return 0;
}