[백준 2096] 내려가기 (C#, C++) - soo:bak

문제 링크

2096번 - 내려가기

설명

N개의 줄에 각각 3개의 숫자가 있고, 첫째 줄부터 마지막 줄까지 내려가며 숫자를 선택합니다. 이동할 때는 현재 열과 같거나 인접한 열로만 갈 수 있습니다. 선택한 숫자 합의 최댓값과 최솟값을 구하는 문제입니다.

접근법

각 줄의 각 열에 도달했을 때의 최대 합과 최소 합을 계산합니다. 왼쪽 열로 이동하려면 이전 줄의 왼쪽이나 가운데 열에서 와야 하고, 가운데 열로 이동하려면 세 열 모두에서 올 수 있으며, 오른쪽 열로 이동하려면 가운데나 오른쪽 열에서 와야 합니다.

N이 최대 10만이므로 전체 배열을 저장하면 메모리 제한을 초과할 수 있습니다. 현재 줄의 값은 바로 이전 줄의 값만 필요하므로, N개의 줄 전체를 저장하지 않고 이전 줄과 현재 줄 두 개의 배열만 번갈아 사용하면 공간을 절약할 수 있습니다.

마지막 줄까지 계산한 후, 세 열 중 최댓값과 최솟값을 각각 출력합니다.

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);

      var maxPrev = new int[3];
      var minPrev = new int[3];

      var first = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      for (var i = 0; i < 3; i++) {
        maxPrev[i] = first[i];
        minPrev[i] = first[i];
      }

      for (var i = 1; i < n; i++) {
        var line = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
        var maxCur = new int[3];
        var minCur = new int[3];

        maxCur[0] = line[0] + Math.Max(maxPrev[0], maxPrev[1]);
        maxCur[1] = line[1] + Math.Max(Math.Max(maxPrev[0], maxPrev[1]), maxPrev[2]);
        maxCur[2] = line[2] + Math.Max(maxPrev[1], maxPrev[2]);

        minCur[0] = line[0] + Math.Min(minPrev[0], minPrev[1]);
        minCur[1] = line[1] + Math.Min(Math.Min(minPrev[0], minPrev[1]), minPrev[2]);
        minCur[2] = line[2] + Math.Min(minPrev[1], minPrev[2]);

        maxPrev = maxCur;
        minPrev = minCur;
      }

      var maxAns = Math.Max(Math.Max(maxPrev[0], maxPrev[1]), maxPrev[2]);
      var minAns = Math.Min(Math.Min(minPrev[0], minPrev[1]), minPrev[2]);
      Console.WriteLine($"{maxAns} {minAns}");
    }
  }
}

C++

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

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

  int n; cin >> n;

  int maxPrev[3], minPrev[3];
  for (int i = 0; i < 3; i++) {
    int v; cin >> v;
    maxPrev[i] = v;
    minPrev[i] = v;
  }

  for (int i = 1; i < n; i++) {
    int cur[3];
    cin >> cur[0] >> cur[1] >> cur[2];
    int maxCur[3], minCur[3];

    maxCur[0] = cur[0] + max(maxPrev[0], maxPrev[1]);
    maxCur[1] = cur[1] + max({maxPrev[0], maxPrev[1], maxPrev[2]});
    maxCur[2] = cur[2] + max(maxPrev[1], maxPrev[2]);

    minCur[0] = cur[0] + min(minPrev[0], minPrev[1]);
    minCur[1] = cur[1] + min({minPrev[0], minPrev[1], minPrev[2]});
    minCur[2] = cur[2] + min(minPrev[1], minPrev[2]);

    for (int j = 0; j < 3; j++) {
      maxPrev[j] = maxCur[j];
      minPrev[j] = minCur[j];
    }
  }

  int maxAns = max({maxPrev[0], maxPrev[1], maxPrev[2]});
  int minAns = min({minPrev[0], minPrev[1], minPrev[2]});
  cout << maxAns << " " << minAns << "\n";

  return 0;
}