[Python] SWEA - 1959 두 개의 숫자열

Isabel·2022년 7월 19일
0

알고리즘 문제풀이

목록 보기
33/36

SWEA 1959 두 개의 숫자열

SWEA 1959

각 길이가 다른 두 개의 숫자열의 서로 마주보는 숫자들을 곱한 뒤 더했을 때 최댓값을 구하는 문제이다.

#testcase
T = int(input())

for i in range(0, T) : 
    #각 숫자열의 길이
    NM = input()

    A = input().split() 
    A = list(map(int, A)) # 배열의 모든 값을 정수형(int)로 변환한 list를 만듦
    B = input().split() 
    B = list(map(int, B))

    # B열의 길이가 더 짧을 경우, A와 B swab (이렇게 하면 항상 B열이 더 긺)
    if len(A) > len(B) :
        B, A = A, B

    arr = []

    for k in range(len(B)-len(A)+1) : 
        sum = 0
        for r in range(len(A)) : 
            sum += A[r] * B[r+k]
        arr.append(sum)  # 각 시도들을 배열에 넣고 그 중에서 제일 큰 값을 출력 

    print(f'#{i+1} {max(arr)}')

조건

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


  • 더 긴 쪽의 양끝을 벗어나서는 안 되기 때문에, 각 testcase마다 시도는 긴 열에서 짧은 열의 길이를 뺀 것보다 1번 더 가능하다.
 e.g.) len(A) = 5, len(B) = 3 --- > try_no = 3
  • 그리고 각 testcase의 한 번의 시도마다 A열과 B열이 곱하는 횟수는 A열의 길이만큼 가능하다.
    시도는 아래와 같이 시행된다.
arr = [A1*B1 + A2*B2 + A3*B3, A1*B2 + A2*B3 + A3*B4, A1*B3 + A2*B4 + A3*B5 ]
  • 위 arr의 값들 중에서 제일 큰 값을 찾는다.

여전히 memory error가 발생한다.
리스트나 변수를 굳이 만들지 않고 코드를 작성하는 법을 익혀야 될 것 같다.

0개의 댓글