https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

문제 설명

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

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

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

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

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

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

[제약 사항]

N 과 M은 3 이상 20 이하이다.

[입력]

가장 첫 줄에는 테스트 케이스의 개수 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

출력

#1 30
#2 63

---

풀이

from collections import deque
# deque : 0을 빼서 왼쪽으로 계속 옮겨야하므로

for i in range(1, int(input()) + 1):
    N, M = map(int, input().split())
    Narr = list(map(int, input().split()))
    Marr = list(map(int, input().split()))
    max = 0  # 연산 최대값

    if N < M:  # 더 작은 쪽에 0만큼 덧붙여주기
        Narr = deque(Narr+[0]*(M-N)) #모자란만큼 0덧붙이기
        for _ in range(M-N+1): # pop을 안한 초기상태 연산 + 0붙은만큼의 pop한 후 연산
            sum = 0  # 연산결과
            for n, m in zip(Narr, Marr): # 각 숫자 곱해서 더하기
                sum += n * m
            if sum > max: max = sum #현재 연산결과가 최대값일 때 최대값 변경
            Narr.appendleft(Narr.pop())

    else:
        Marr = deque(Marr+[0]*(N-M))
        for _ in range(N-M+1):
            sum = 0  # 연산결과
            for n, m in zip(Narr, Marr):
                sum += n * m
            if sum > max: max = sum
            Marr.appendleft(Marr.pop())

    print(f"#{i} {max}")

1. 크기가 더 작은 리스트쪽에서 부족한만큼 0추가하고 deque로 만들기
   1-2. 0을 pop한 후 왼쪽으로 넣어 숫자를 이동시켜야함
2. 각 자리 곱셈 후 더하면서 최대값보다 큰지 비교
3. 숫자 이동 위해 pop
4. 최대값 출력

for _ in range(M-N+1): # pop을 안한 초기상태 연산 + 0붙은만큼의 pop한 후 연산

예를 들어 [1,2,3,0,0]과 [1,2,3,4,5]가 있을 때

• 연산하는 경우는 [1,2,3,0,0], [0,1,2,3,0], [0,0,1,2,3]
  총 M-N(0의 개수)+1(기본 상태)개 => 세 개