SWEA - 두 개의 숫자열(1959)

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 가 주어진다.

 

 

접근방식

a_arr와 b_arr를 각각 받음

ans = 0, arr = []로 선언

만약 N <= M이면(a 배열의 길이보다 b 배열의 길이가 크면) min_num = N으로 선언하고 range_value를 M-N+1로 선언

반대일 경우 반대값으로 선언

이렇게 해주는 이유는 먼저 배열의 길이가 긴 곳의 길이에서 짧은 곳의 길이를 빼고 +1을 한 범위만큼 for문을 돌리면서 그 안에 배열의 길이가 짧은 값만큼 for문을 돌려야 함

(ex: N = 5, M = 3이면 a배열의 길이는 5, b배열의 길이는 3이므로 b[0]xa[0], b[1]xa[1], b[2]xa[2]를 해주고 그 다음에 b[1]xa[0], b[2]xa[1], b[3]xa[2], 그 다음에 b[2]xa[0], b[3]xa[1], b[4]xa[2] 인데 식을 보면 a의 인덱스값은 바뀌지 않고 고정됨을 알 수 있음. 그리고 총 3번의 연산을 반복해야하므로 N-M+1 = 5-3+1 = 3이므로 범위를 0~3으로 잡으면 연산을 3번 반복할 것임)

내부 수식은 한 번만 써보면 이해가 가능하므로 설명 생략

 

코드

T = int(input())
for i in range(1, T+1):
    N, M = map(int, input().split())
    a_arr = list(map(int, input().split()))
    b_arr = list(map(int, input().split()))
    ans = 0
    arr =[]
    
    if N <= M:
        min_num = N
        range_value = M-N+1
    else:
        min_num = M
        range_value = N-M+1
        
    for j in range(range_value):
        for k in range(min_num):
            if min_num == N:
                val = a_arr[k] * b_arr[j+k]
                ans += val
            else:
                val = b_arr[k] * a_arr[j+k]
                ans += val
        arr.append(ans)
        ans = 0
    print('#'+str(i), max(arr))