[백준 24349] МЕД (C#, C++) - soo:bak

문제 링크

24349번 - МЕД

설명

세 집 사이를 이동하며 n번 꿀을 먹을 때, 이동 거리의 최솟값을 구하는 문제입니다.

접근법

집은 3곳이고 매 이동마다 다른 집으로만 갈 수 있습니다. 첫 집에서 시작해 이동 횟수를 단계로 둔 동적 계획법으로 최소 이동 거리를 계산합니다.

마지막 위치는 상관없으므로 마지막 단계에서 세 집 중 최소값을 출력합니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var parts = Console.ReadLine()!.Split();
    var n = int.Parse(parts[0]);
    var a = int.Parse(parts[1]);
    var b = int.Parse(parts[2]);
    var c = int.Parse(parts[3]);

    var dist = new int[3, 3];
    dist[0, 1] = dist[1, 0] = a;
    dist[0, 2] = dist[2, 0] = b;
    dist[1, 2] = dist[2, 1] = c;

    var steps = n - 1;
    var inf = 1_000_000_000;
    var dp = new int[steps + 1, 3];
    for (var i = 0; i <= steps; i++) {
      for (var j = 0; j < 3; j++)
        dp[i, j] = inf;
    }
    dp[0, 0] = 0;

    for (var s = 0; s < steps; s++) {
      for (var u = 0; u < 3; u++) {
        var cur = dp[s, u];
        if (cur == inf) continue;
        for (var v = 0; v < 3; v++) {
          if (u == v) continue;
          var val = cur + dist[u, v];
          if (val < dp[s + 1, v]) dp[s + 1, v] = val;
        }
      }
    }

    var ans = dp[steps, 0];
    if (dp[steps, 1] < ans) ans = dp[steps, 1];
    if (dp[steps, 2] < ans) ans = dp[steps, 2];

    Console.WriteLine($"{ans / 100} {ans % 100}");
  }
}

C++

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

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

  int n, a, b, c; cin >> n >> a >> b >> c;

  int dist[3][3] = {};
  dist[0][1] = dist[1][0] = a;
  dist[0][2] = dist[2][0] = b;
  dist[1][2] = dist[2][1] = c;

  int steps = n - 1;
  int inf = 1e9;
  int dp[101][3];
  for (int i = 0; i <= steps; i++) {
    for (int j = 0; j < 3; j++)
      dp[i][j] = inf;
  }
  dp[0][0] = 0;

  for (int s = 0; s < steps; s++) {
    for (int u = 0; u < 3; u++) {
      if (dp[s][u] == inf) continue;
      for (int v = 0; v < 3; v++) {
        if (u == v) continue;
        int val = dp[s][u] + dist[u][v];
        if (val < dp[s + 1][v]) dp[s + 1][v] = val;
      }
    }
  }

  int ans = min(dp[steps][0], min(dp[steps][1], dp[steps][2]));
  cout << ans / 100 << " " << ans % 100 << "\n";

  return 0;
}