수열 만들기

1. 문제

수열에 있는 연속된 원소들의 합을 이용하여 새로운 수열을 만들 수 있다. 예를 들어 1, 2, 3, 4, 5와 같은 수열이 있다고 했을 때, 1, 2를 합쳐서 3, 3, 4, 5 또는 2, 3, 4를 합쳐서 1, 9, 5를 만들 수 있다. 모든 원소를 합쳐서 15 등의 수열을 만들 수도 있다. 

 

두 개의 수열이 주어질 때, 두 수열을 같은 수열로 만들 수 있을 때, 만들수 있는 가장 긴 같은 수열의 길이를 구하는 것이다.

 

2. 입력

3. 출력

두 수열을 똑같은 수열로 만들 수 있다면 그 수열의 최대 길이를, 만들 수 없다면 -1을 출력한다.

4. 알고리즘 : 그리디, 투포인터

첫번째로 두 수열의 총합이 다르다면 절대로 같은 수열로 만들 수 없다.

 

해당 확인이 끝났다면 투 포인터를 이용해서 원소들을 합치면서 비교한다. 첫번째 수열의 위치, 두번째 수열의 위치를 가리키는 두개의 포인터를 이용한다. 첫번째 수열의 누적합이 큰 경우에는 두 번째 수열의 포인터를 이동하고 반대의 경우에는 첫번째 수열의 포인터를 이동한다. 

5. 소스코드

# 입력처리
len1 = int(input())
arr1 = list(map(int, input().split()))
len2 = int(input())
arr2 = list(map(int, input().split()))

# 합이 다른 경우에는 절대로 같은 수열로 만들 수 없다.
if sum(arr1) != sum(arr2):
    print(-1)
else:
	# 누적합 배열 생성
    arr1_sum = [i for i in arr1]
    arr2_sum = [i for i in arr2]
    for i in range(1, len1):
        arr1_sum[i] += arr1_sum[i-1]
    for i in range(1, len2):
        arr2_sum[i] += arr2_sum[i-1]
    
    # 투포인터를 사용한다.
    cnt, i, j = 0, 0, 0
    while i < len1 and j < len2:
        if arr1_sum[i] == arr2_sum[j]: # 같을 경우 길이 + 1
            cnt += 1
            i += 1
            j += 1
        elif arr1_sum[i] > arr2_sum[j]:
            j += 1
        else :
            i += 1
    # 두 누적합 배열에서 같은 수의 개수인 cnt가 만들 수 있는 최대수열의 길이에 대응된다.
    print(cnt)