작성일 :

문제 링크

18795번 - 이동하기 3

설명

좌표 (0, 0) 에서 출발하여 (N, M) 까지 이동하면서 경로를 따라 쓰레기를 모으는 문제입니다.

이동할 수 있는 방향은 오른쪽 또는 아래쪽 뿐이며,

각 방향으로 이동할 때마다 해당 위치에 있는 쓰레기를 가져가야 합니다.

최종적으로 (N, M) 까지 도달했을 때 가져가야 하는 쓰레기의 총합을 최소화하는 것이 목표입니다.


격자판을 이동하는 경로는 다음과 같은 특성을 가집니다:

  • 오른쪽 또는 아래쪽 으로만 이동할 수 있기 때문에, (0, 0) 에서 (N, M) 까지 이동하는 방법은 하나로 정해져 있습니다.
  • 반드시 M 번 오른쪽으로 이동하고, N 번 아래쪽으로 이동해야 최종 목적지에 도달할 수 있습니다.
  • 따라서 경로를 선택하거나 최적화할 필요가 없으며, 이동 경로는 고정되어 있습니다.

이때, 이동 과정에서 가져가야 하는 쓰레기의 양은 다음과 같습니다:

  • 아래 방향으로 이동할 때마다 해당하는 A 배열의 값을 가져갑니다.
  • 오른쪽 방향으로 이동할 때마다 해당하는 B 배열의 값을 가져갑니다.

결국, (N, M) 까지 도달하는 데 필요한 쓰레기의 양은

  • A 배열에 있는 모든 수와 B 배열에 있는 모든 수를 각각 한 번씩 더한 값과 같습니다.


접근법

  • 먼저 nm을 입력받습니다.
  • 이후 n개의 A 배열 값과 m개의 B 배열 값을 차례대로 입력받습니다.
  • A 배열의 합과 B 배열의 합을 각각 구해 더한 뒤 출력하면 됩니다.

Code

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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];

    var a = Console.ReadLine().Split().Select(long.Parse).ToArray();
    var b = Console.ReadLine().Split().Select(long.Parse).ToArray();

    long sum = a.Sum() + b.Sum();
    Console.WriteLine(sum);
  }
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

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

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

  ll sum = 0;
  for (int i = 0; i < n + m; i++) {
    int a; cin >> a;
    sum += a;
  }

  cout << sum << "\n";

  return 0;
}