SWEA 1959번: 두 개의 숫자열 (D2) - Python 풀이

문제 설명

SW Expert Academy

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
...

input.txt

출력

#1 30
#2 63
...

output.txt

풀이 과정

1. 둘 중 길이가 더 긴 것과 짧은 것을 구분합니다.
2. 긴 것의 맨 왼쪽 위치에서부터 짧은 것을 한 칸씩 움직이며 마주보게 하고, 마주본 숫자끼리 곱한 뒤 모두 더합니다. << 가능한 모든 경우의 수 확인하는 것
3. 2번에서 계산한 모든 값 중 최댓값을 출력합니다.

정답 코드

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N, M = map(int, input().split())
    Aj = list(map(int, input().split()))
    Bj = list(map(int, input().split()))
 	
    # 둘 중 더 큰 값과 작은 값 구분
    big = max(N, M)
    small = min(N, M)
    # (큰 값에서 작은 값 빼고 + 1)한 횟수만큼 Aj Bj가 마주보게 됩니다
    value = big - small + 1
    answers = [0 for _ in range(value)]
 
    # 길이에 따라 Bigj와 Smallj 설정
    Bigj = []
    Smallj = []
    if big == N:
        Bigj = Aj
        Smallj = Bj
    else:
        Bigj = Bj
        Smallj = Aj
 	
    # value번 마주볼 수 있음
    for v in range(value):
    	# small개가 마주본다
        for s in range(small):
            # 곱한 값을 더해서 answers에 업데이트
            answers[v] += Bigj[v+s] * Smallj[s]
 	# answers 중 최댓값 출력
    print("#%d %d" %(test_case, max(answers)))

이지한 문제였습니다.

이상입니다.