백준 4929 (C++) 수열 걷기

최초 업로드: 2025-09-14 13:27:53

최근 수정 시간: 2025-09-14 13:27:53

게시자: rlatjwls3333

카테고리: 백준

# [Silver I] 수열 걷기

[문제 링크](https://www.acmicpc.net/problem/4929)

## 문제 설명

길이가 유한하고, 오름차순 순서로 되어있는 두 수열이 주어진다. 두 수열에 공통으로 들어있는 원소는 교차점으로 생각할 수 있다.

아래는 두 수열과 교차점은 굵게 나타낸 것이다.

수열 1 = 3 5 7 9 20 25 30 40 55 56 57 60 62

수열 2 = 1 4 7 11 14 25 44 47 55 57 100

이 두 수열은 다음과 같이 걸을 수 있다.

방문한 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하시오. 위의 예에서 3, 5, 7, 9, 20, 25, 44, 47, 55, 56, 57, 60, 62와 같이 걷는다면 합이 450으로 최대가 된다.

## 입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 두 줄로 이루어져 있다.

각 줄의 첫 번째 수는 수열의 길이이다. 그 다음에는 수열의 원소가 순서대로 주어진다. 수열의 길이는 1이상이고, 10,000을 넘지 않는다. 수열에 들어있는 모든 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

입력의 마지막 줄에는 0이 하나 주어진다.

## 출력

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

## 풀이
A의 수를 맵에 넣고, 교차점 이전에 어떤 경로로 올 지 선택하며 풀었다.

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    while(true) {
        int n; cin >> n;
        if(!n) break;

map<int, int> idx;
 vector<int> a(n);
 for(int i=0;i<n;i++) {
 cin >> a[i];
 idx[a[i]]=i;
 }

int sum=0, lastA=0, lastB=0;
 int m; cin >> m;
 vector<int> b(m);
 for(int i=0;i<m;i++) {
 cin >> b[i];
 if(idx.count(b[i])) {
 sum += max(accumulate(a.begin()+lastA, a.begin()+idx[b[i]]+1, 0), accumulate(b.begin()+lastB, b.begin()+i+1, 0));
 lastA = idx[b[i]]+1;
 lastB = i+1;
 }
 }
 if(lastA<n || lastB<m) sum += max(accumulate(a.begin()+lastA, a.end(), 0), accumulate(b.begin()+lastB, b.end(), 0));
 cout << sum << '\n';
 }
}
```