[SWEA D2 / Python] 두 개의 숫자열

알고리즘 유형 : 구현
풀이 없이 스스로 풀었나요? : ⭕

---

SWEA 두 개의 숫자열 문제 보기

문제 설명

N 개의 숫자로 구성된 숫자열 Ai (i=1~N) 와 M 개의 숫자로 구성된 숫자열 Bj (j=1~M) 가 있다.

아래는 N =3 인 Ai 와 M = 5 인 Bj 의 예이다.

Ai 나 Bj 를 자유롭게 움직여서 숫자들이 서로 마주보는 위치를 변경할 수 있다.

단, 더 긴 쪽의 양끝을 벗어나서는 안 된다.

서로 마주보는 숫자들을 곱한 뒤 모두 더할 때 최댓값을 구하라.

위 예제의 정답은 아래와 같이 30 이 된다.

입력

• 가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.

• 각 테스트 케이스의 첫 번째 줄에 N 과 M 이 주어지고, 두 번째 줄에는 Ai, 세 번째 줄에는 Bj 가 주어진다.

출력

• 출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.
  (t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

입출력 예

- 입력

10
3 5
1 5 3
3 6 -7 5 4
7 6
6 0 5 5 -1 1 6
-4 1 8 7 -9 3
5 15
-8 4 6 -9 -1
-1 1 0 -2 10 10 0 2 5 2 10 7 -9 7 -8
11 20
3 -8 4 0 -1 -4 8 3 7 -3 1
3 10 0 1 10 0 -8 -6 9 -7 -1 1 -1 4 10 6 0 -8 -5 0
11 16
-6 0 -1 7 5 -1 -3 0 -9 8 4
0 -6 1 1 8 -8 0 -7 4 -7 -8 -2 1 4 0 -10
3 16
8 9 0
-4 9 -7 -1 -8 3 1 -6 -8 5 2 -7 -9 -10 8 9
11 3
3 -4 -7 7 -2 5 5 0 -2 -8 4
-1 1 3
14 6
-9 9 0 -7 8 10 7 -3 2 3 0 0 0 -2
8 1 -9 3 0 -7
17 10
-6 -1 -4 2 -5 1 -10 -9 8 -9 -6 1 10 0 -5 -8 1
7 6 2 7 -8 4 8 10 -2 9
11 9
8 6 -2 0 0 5 10 2 -10 -8 -10
10 -9 -7 -1 0 8 0 10 3

- 출력

#1 30
#2 63
#3 140
#4 181
#5 63
#6 58
#7 22
#8 120
#9 96
#10 70

솔루션

긴 배열가 짧은 배열을 구분하고, zip 함수를 통해 두 리스트를 매치시킨다
예를 들어 [1,2,3,4,5]와 [6,7,8] 과 같은 리스트가 있을 경우 zip을 활하면
[(1,6), (2,7), (3,8)]과 같이 만들 수 있다.
이를 이용하여 곱을 구하고 짧은 리스트 맨앞에 0을 추가하여 한 칸 이동한 효과를 주었다.

코드

import sys

input = sys.stdin.readline

T = int(input())
for test_case in range(1, T + 1):
    n, m = map(int, input().split())
    res = -2147000000 # 정수형 최소값

    if n > m:
        long, short = n, m
        long_arr = list(map(int, input().split()))
        short_arr = list(map(int, input().split()))
    else:
        long, short = m, n
        short_arr = list(map(int, input().split()))
        long_arr = list(map(int, input().split()))

    dif = long - short + 1 # 배열의 길이 차이
    for _ in range(dif): 
        tmp = 0
        for a, b in zip(long_arr, short_arr): # zip을 사용하여 두 배열을 묶음
            tmp += (a * b)
        if tmp > res:
            res = tmp
        short_arr.insert(0, 0) # 배열의 가장 앞에 0을 추가

    print("#{} {}".format(test_case, res))

---