[SWEA] 1959 : 두 개의 숫자열 (Python/파이썬)

문제 링크

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

문제

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

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

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

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

[제약 사항]

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

---

정답 및 풀이

t = int(input())

for tc in range(t):
    n, m = map(int, input().split())

    if n <= m :
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))
    else :
        b = list(map(int, input().split()))
        a = list(map(int, input().split()))

    result = []
    for i in range(len(b)-len(a)+1):
        cnt = 0
        for j in range(len(a)):
            cnt += b[i + j] * a[j]
        result.append(cnt)
    print(f'#{tc+1} {max(result)}')

1. t = int(input())
   • 테스트 케이스 개수를 입력받는다.
2. for tc in range(t):
   • 테스트 케이스 수만큼 반복한다.
   • 출력이 #1, #2 형식이므로 0부터 시작해도 +1 해서 출력한다.
3. n, m = map(int, input().split())
   • 두 숫자열의 길이 n, m을 입력받는다.
4. if n <= m:b = list(map(int, input().split()))
   • n이 더 작은 경우, 첫 번째 입력을 a(짧은 배열), 두 번째 입력을 b(긴 배열)로 받는다.
5. a = list(map(int, input().split()))
6. else:a = list(map(int, input().split()))
   • n이 더 큰 경우에는 입력 순서를 바꿔서 항상 a가 더 짧게 만든다.
7. b = list(map(int, input().split()))
8. result = []
   • 위치마다 계산한 곱의 합을 저장할 리스트다.
9. for i in range(len(b) - len(a) + 1):
   • 짧은 배열 a가 긴 배열 b 위에서 움직일 수 있는 모든 시작 위치를 반복한다.
   • 가능한 이동 횟수 = len(b) - len(a) + 1 이다.
10. cnt = 0
    • 현재 위치(i)에서의 곱셈 결과를 저장할 변수다.
11. for j in range(len(a)):
    • 짧은 배열 a의 모든 원소를 순회한다.
12. cnt += b[i + j] * a[j]
    • b의 i+j 번째 원소와 a의 j 번째 원소를 곱해서 누적한다.
13. result.append(cnt)
    • 한 이동 위치에서 계산한 곱의 합을 result 리스트에 저장한다.
14. print(f'#{tc+1} {max(result)}')
    • result 중 최댓값을 출력한다.
    • 문제에서 요구하는 출력 형식에 맞춰 #tc로 출력한다.

---