BOJ 4929 - 수열 걷기

문제

BOJ 4929 - 수열 걷기

오름차순으로 정렬된 두 수열을 걸을 때 얻을 수 있는 최대 합을 구하는 문제다. 두 수열을 동시에 걸으며 공통 원소에서는 두 경로 중 유리한 쪽으로 전환할 수 있다. 목표는 두 수열 중 하나의 경로를 선택하되, 공통 원소에서 경로를 전환하면서 합계를 최대화하는 것이다.

입력

첫 번째 수열의 크기와 원소, 두 번째 수열의 크기와 원소가 주어진다. 입력은 첫 번째 수열 크기가 0일 때 종료된다. 각 수열은 오름차순으로 정렬되어 있다.

출력

각 테스트 케이스에 대해 얻을 수 있는 최대 합을 출력한다.

예제

풀이

두 포인터(two pointer) 기법으로 두 수열을 동시에 순회하며, 공통 원소에서 누적 합이 더 큰 경로를 선택한다.

1. 두 수열 v1, v2와 각각의 누적 합 sum[0], sum[1]을 초기화한다.
2. 두 포인터 i, j를 사용해 두 수열을 동시에 순회한다.
3. v1[i] < v2[j]이면 수열 1의 현재 원소를 sum[0]에 더하고 i를 증가시킨다.
4. v1[i] > v2[j]이면 수열 2의 현재 원소를 sum[1]에 더하고 j를 증가시킨다.
5. v1[i] == v2[j]이면 공통 원소이므로, max(sum[0], sum[1]) + 공통 원소 값을 두 누적 합 모두에 저장하고 양쪽 포인터를 모두 증가시킨다.
6. 한 수열이 소진되면 나머지 수열을 해당 누적 합에 모두 더한다.
7. max(sum[0], sum[1])을 출력한다.

핵심 아이디어: 공통 원소에서 두 경로가 합류하므로, 합류 시점에 더 큰 누적 합을 선택해 두 경로 모두 같은 값으로 동기화한다. 이후 다시 수열이 갈라질 때 각자 독립적으로 합산되며, 최종적으로 더 큰 누적 합이 정답이 된다.

코드

#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(false);
 
  int count;
  while (cin >> count)
  {
    if (!count)
      break;
    vector<int> v1(count);
    for (int i = 0; i < count; i++)
      cin >> v1[i];
    cin >> count;
    vector<int> v2(count);
    for (int i = 0; i < count; i++)
      cin >> v2[i];
 
    size_t i = 0, j = 0;
    vector<int> sum(2, 0);
    while (i < v1.size() && j < v2.size())
    {
      if (v1[i] < v2[j])
        sum[0] += v1[i++];
      else if (v1[i] > v2[j])
        sum[1] += v2[j++];
      else
      {
        sum[0] = max(sum[0], sum[1]) + v1[i];
        sum[1] = sum[0];
        i++;
        j++;
      }
    }
    while (i < v1.size())
      sum[0] += v1[i++];
    while (j < v2.size())
      sum[1] += v2[j++];
 
    cout << max(sum[0], sum[1]) << "\n";
  }
}

복잡도

• 시간: O(N + M) — N, M은 각 수열의 길이. 두 포인터가 각 수열을 한 번씩 순회
• 공간: O(N + M) — 두 수열을 벡터에 저장