[백준 21923] 곡예 비행 (C#, C++) - soo:bak

문제 링크

21923번 - 곡예 비행

설명

격자의 왼쪽 아래에서 출발해 위나 오른쪽으로만 이동하는 상승 비행을 하다가, 어떤 칸에서 방향을 바꿔 아래나 오른쪽으로만 이동하는 하강 비행으로 오른쪽 아래까지 가는 경로에서 점수 합의 최댓값을 구하는 문제입니다. 전환하는 칸은 상승과 하강 양쪽에서 모두 점수에 포함됩니다.

접근법

경로는 상승 구간과 하강 구간으로 나뉩니다. 상승은 왼쪽 아래에서 시작해 위나 오른쪽으로만 가고, 하강은 아래나 오른쪽으로만 가서 오른쪽 아래에 도착합니다. 두 구간은 어떤 한 칸에서 만나며, 그 칸이 전환점입니다.

전환점을 어디로 정하느냐에 따라 총 점수가 달라집니다. 모든 칸에 대해 “왼쪽 아래에서 이 칸까지 오는 최대 점수”와 “이 칸에서 오른쪽 아래까지 가는 최대 점수”를 미리 구해두면, 둘을 더한 값이 그 칸을 전환점으로 삼았을 때의 총 점수가 됩니다. 전환점은 양쪽 경로에 모두 포함되므로 점수가 자연스럽게 두 번 더해집니다.

상승 경로의 최대 점수는 왼쪽 아래 칸부터 시작해 아래에서 위로, 왼쪽에서 오른쪽으로 채워나갑니다. 각 칸에 도달하려면 아래 칸이나 왼쪽 칸에서 와야 하므로, 둘 중 큰 값에 현재 칸 점수를 더합니다.

하강 경로의 최대 점수는 오른쪽 아래 칸부터 시작해 아래에서 위로, 오른쪽에서 왼쪽으로 채워나갑니다. 각 칸에서 출발하면 아래 칸이나 오른쪽 칸으로 가야 하므로, 둘 중 큰 값에 현재 칸 점수를 더합니다.

이렇게 구한 상승 점수와 하강 점수를 모든 칸에 대해 더해보고, 그 중 가장 큰 값을 출력합니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var first = Console.ReadLine()!.Split();
    var n = int.Parse(first[0]);
    var m = int.Parse(first[1]);

    var grid = new long[n, m];
    for (var i = 0; i < n; i++) {
      var parts = Console.ReadLine()!.Split();
      for (var j = 0; j < m; j++)
        grid[i, j] = long.Parse(parts[j]);
    }

    var neg = long.MinValue / 4;

    var up = new long[n, m];
    for (var i = 0; i < n; i++)
      for (var j = 0; j < m; j++)
        up[i, j] = neg;
    up[n - 1, 0] = grid[n - 1, 0];
    for (var i = n - 1; i >= 0; i--) {
      for (var j = 0; j < m; j++) {
        if (i + 1 < n)
          up[i, j] = Math.Max(up[i, j], up[i + 1, j] + grid[i, j]);
        if (j - 1 >= 0)
          up[i, j] = Math.Max(up[i, j], up[i, j - 1] + grid[i, j]);
      }
    }

    var down = new long[n, m];
    for (var i = 0; i < n; i++)
      for (var j = 0; j < m; j++)
        down[i, j] = neg;
    down[n - 1, m - 1] = grid[n - 1, m - 1];
    for (var i = n - 1; i >= 0; i--) {
      for (var j = m - 1; j >= 0; j--) {
        if (i + 1 < n)
          down[i, j] = Math.Max(down[i, j], down[i + 1, j] + grid[i, j]);
        if (j + 1 < m)
          down[i, j] = Math.Max(down[i, j], down[i, j + 1] + grid[i, j]);
      }
    }

    var ans = neg;
    for (var i = 0; i < n; i++)
      for (var j = 0; j < m; j++)
        ans = Math.Max(ans, up[i, j] + down[i, j]);

    Console.WriteLine(ans);
  }
}

C++

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

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;

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

  int n, m; cin >> n >> m;

  vvll a(n, vll(m));
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      cin >> a[i][j];

  const ll neg = -(1LL << 60);

  vvll up(n, vll(m, neg));
  up[n - 1][0] = a[n - 1][0];
  for (int i = n - 1; i >= 0; i--) {
    for (int j = 0; j < m; j++) {
      if (i + 1 < n) up[i][j] = max(up[i][j], up[i + 1][j] + a[i][j]);
      if (j - 1 >= 0) up[i][j] = max(up[i][j], up[i][j - 1] + a[i][j]);
    }
  }

  vvll down(n, vll(m, neg));
  down[n - 1][m - 1] = a[n - 1][m - 1];
  for (int i = n - 1; i >= 0; i--) {
    for (int j = m - 1; j >= 0; j--) {
      if (i + 1 < n) down[i][j] = max(down[i][j], down[i + 1][j] + a[i][j]);
      if (j + 1 < m) down[i][j] = max(down[i][j], down[i][j + 1] + a[i][j]);
    }
  }

  ll ans = neg;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      ans = max(ans, up[i][j] + down[i][j]);

  cout << ans << "\n";

  return 0;
}