[백준/파이썬][Silver II] 수열 걷기 - 4929

[Silver II] 수열 걷기 - 4929

문제 링크

성능 요약

메모리: 110888 KB, 시간: 104 ms

분류

구현

제출 일자

2025년 3월 6일 20:18:06

문제 설명

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

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

수열 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

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

1. 두 수열중 하나의 첫 번째 원소에서 걷기를 시작한다. 걷는 것은 앞으로만 걸을 수 있다.
2. 교차점에 도착했을 때는, 현재 수열에서 계속 걸을지, 다른 수열로 갈아탈지 결정할 수 있다.

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

입력

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

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

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

출력

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

풀이

def sol_4929() :
    while True :
        n, *arr1 = map(int, input().split())
        if n == 0 :
            break
        m, *arr2 = map(int, input().split())

        arr1.reverse()
        arr2.reverse()

        ans = 0
        c = [0, 0]

        while True :
            if not arr1 or not arr2 :
                ans += max(c[0] + sum(arr1), c[1] + sum(arr2))
                break

            if arr1[-1] < arr2[-1] :
                c[0] += arr1.pop()
            elif arr1[-1] > arr2[-1] :
                c[1] += arr2.pop()
            else :
                ans += max(c) + arr1.pop()
                arr2.pop()
                c = [0, 0]

        print(ans)

sol_4929()

수열을 뒤집어서 스택처럼 활용하는 풀이 방법을 찾아보고 이해가 바로 되었다.

수열 자체가 이미 정렬이 되어 있기 때문에 뒤집어서 끝에서 부터 하나씩 꺼내어 숫자를 비교하여서, 겹치는 숫자가 등장하기 전까지 각 수열에서 해당하는 칸에 숫자를 더해간다. 

동일한 숫자가 등장하면 더 큰 수를 가진 수열의 합과 겹치는 숫자를 ans에 더하고 수열의 합을 계산한 c배열을 초기화 한다.

이러한 방법을 활용하여 문제를 해결하는 코드를 보니 이해가 되었다.