코드
from typing import List
def solve(n: int, m: int, a_list: List[int], b_list: List[int]) -> int:
result = 0
if n >= m:
for i in range(0, n-m+1):
nums = a_list[i:i+m]
result = max(result, sum([x*y for x, y in zip(nums, b_list)]))
else:
for i in range(0, m-n+1):
nums = b_list[i:i+n]
result = max(result, sum([x*y for x, y in zip(nums, a_list)]))
return result
if __name__ == '__main__':
T = int(input())
for test_case in range(1, T + 1):
n, m = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
print(f'#{test_case} {solve(n, m, a_list, b_list)}')결과
ChatGPT Code
T = int(input()) # 테스트 케이스의 개수
for t in range(1, T+1):
N, M = map(int, input().split()) # N과 M 입력
Ai = list(map(int, input().split())) # Ai 입력
Bj = list(map(int, input().split())) # Bj 입력
max_length = max(N, M) # 더 긴 숫자열의 길이
max_value = 0 # 최댓값 초기화
for i in range(max_length - N + 1):
for j in range(max_length - M + 1):
total = 0
for k in range(N):
total += Ai[k] * Bj[k]
if total > max_value:
max_value = total
print(f'#{t} {max_value}')ChatGPT 문제풀이
해당 문제는 두 개의 숫자열에서 숫자들을 서로 마주보는 위치를 변경하여 곱한 뒤 최댓값을 구하는 문제입니다. 이를 해결하기 위해 다음과 같은 접근 방법을 사용할 수 있습니다:
주어진 숫자열 Ai와 Bj를 각각 리스트로 저장합니다.
더 긴 숫자열의 길이를 변수 max_length에 저장합니다.
최댓값을 저장할 변수 max_value를 0으로 초기화합니다.
i를 0부터 max_length - N까지 반복하면서 다음을 수행합니다:
5. j를 0부터 max_length - M까지 반복하면서 다음을 수행합니다:
현재 i와 j값을 기준으로 Ai와 Bj를 곱한 결과를 저장할 변수 total을 0으로 초기화합니다.
k를 0부터 N-1까지 반복하면서 다음을 수행합니다:
8. 현재 위치 i+k와 j+k에 있는 Ai[k]와 Bj[k]를 곱한 값을 total에 더합니다.
total이 max_value보다 크다면 max_value를 total로 업데이트합니다.
max_value를 출력합니다.
ChatGPT 문제풀이와 비교
ChatGPT 코드 전체 시간복잡도: O(T (N - M + 1)^2 N)
내 코드 전체 시간복잡도: O(T (n - m + 1) min(n, m))
내 코드가 더 효율이 좋다.
문제출처 & 깃허브
