[SWEA] 1959. 두 개의 숫자열_python

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpoFaAS4DFAUq 

SW Expert Academy

 

* 문제의 저작권은 SW Expert Academy에 있습니다.

---

1. 문제

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부터 시작한다.)

 

 

 

2. 내 풀이

T = int(input())
for tc in range(1, T+1):
    n, m = map(int, input().split())
    n_list = list(map(int, input().split()))
    m_list = list(map(int, input().split()))

    # 1) 길이 비교
    if len(n_list) >= len(m_list):
        long = n_list
        short = m_list
    else:
        long = m_list
        short = n_list

    # 2) 곱해서 리스트에 넣기
    multi_list = []  # 곱한 값 넣어줄 리스트
    cnt = len(long) - len(short) + 1  # 비교할 횟수
    for i in range(cnt):
        multi = 0
        for j in range(len(short)):
            multi += long[i+j] * short[j]
        multi_list.append(multi)

    # 3) 최댓값 찾기
    result = 0
    for res in multi_list:
        if res > result:
            result = res

    print(f'#{tc} {result}')

-> 2)와 3)을 합쳐서 코드를 더 짧게 줄일 수 있다.

-> 곱한 값을 다 구해서 리스트에 넣지 않고, 큰 값을 max 값으로 계속 바꿔 나가는 방식으로 구할 수 있다.

 

 

 

3. 다른 풀이

t = int(input())
for tc in range(1, t+1):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    if len(a) > len(b):
        big, small = a, b
    else:
        big, small = b, a

    max_total = 0
    for i in range(abs(len(a) - len(b))+1):
        total = 0
        for j in range(len(small)):
            total += small[j] * big[i+j]
        if max_total < total:
            max_total = total
    
    print(f'#{tc} {max_total}')