1959

1959. 두 개의 숫자열

N개의 숫자로 구성된 숫자열 $A_{i}$ (i=1~N)와 M개의 숫자로 구성된 숫자열 $B_{j}$ (j=1~M)가 있다.
아래는 N이 3인 $A_{i}$와 M이 5인 $B_{j}$의 예이다.

$A_{i}$ = | 1 | 5 | 3 |

$B_{j}$ = | 3 | 6 | -7 | 5 | 4 |

$A_{i}$나 $B_{j}$를 자유롭게 움직여서 숫자들이 서로 마주보는 위치를 변경할 수 있다.
단, 더 긴 쪽의 양 끝을 벗어나서는 안 된다.

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

$A_{i}$			1	5	3
			x	x	x
$B_{j}$	3	6	-7	5	4
result			-7	25	12	30

[제약사항]

N과 M은 3이상 20이하이다.

[입력]

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄애 N과 M이 주어지고,
두 번째 줄에는 $A_{i}$,
세 번째 줄에는 $B_{j}$가 주어진다.

[출력]

출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.
(t는 테스트 케이스의 번호를 의미하며, 1부터 시작한다.)

코딩

T = int(input())						# 입력 받은 값을 정수형으로 변환시켜 T에 저장(테스트 케이스)

for i in range(1, T+1):					# 1부터 T까지 1씩 증가하는 반복문
    N, M = map(int, input().split())	# 공백을 기준으로 연속으로 값을 입력 받아 정수형으로 변환시켜 N, M에 저장
    
    if 3 <= N <= 20 and 3 <= M <= 20:	# 제약사항 조건
        A_li = list(map(int, input().split()))
        								# 문제의 숫자열 A를 리스트 형태로 구성
        B_li = list(map(int, input().split()))
        								# 문제의 숫자열 B를 리스트 형태로 구성
        max = 0							# 최댓값을 받을 변수를 선언 후 0으로 초기화
        if N > M:
        # 기본 틀은 N보다 M이 항상 큰 형태로 구성할 예정이기 때문에 만약 입력 받은 값인 M이 N보다 크다면 
            N, M = M, N
            A_li, B_li = B_li, A_li
            							# 각각의 변수와 리스트의 정보를 스왑해줌
            
        for j in range(M - N + 1):		# 0부터 입력 받은 값 중 큰 값(M)에서 작은 값(N)을 뺀 값까지 1씩 증가하는 반복문
        # 최댓값을 구하기 위해서 작은 리스트가 큰 리스트에 맞춰 한 칸씩 움직여 줘야하기 때문에
        # 두 리스트의 차 만큼 반복해서 모든 경우의 수를 찾아 최댓값을 찾음
            sum = 0						# 마주보고 있는 값을 곱하고 더한 값을 저장하기 위한 변수를 선언하고 0으로 초기화
            for k in range(N):			# 0부터 N-1까지 1씩 증가하는 반복문
            							# 마주보고 있는 수 만큼 반복하기 위한 반복문
                sum += A_li[k] * B_li[k + j]
		# A 리스트와 B 리스트 각 인덱스에 맞는 값을 곱한 뒤에 sum에 저장
		# 작은 리스트인 B 리스트에 인덱스에 j가 더해져 있는 이유는 최댓값을 찾기 위해 
		# 큰 리스트의 끝까지 한 칸씩 이동하면서 값을 비교해봐야 하기 때문에
            if max <= sum:				# sum의 값이 max보다 크거나 같을 경우
                max = sum				# 최댓값인 max에 sum을 넣어줌
        print('#{} {}'.format(i, max))	# format 함수를 사용해서 테스트 케이스 번호와 최댓값을 출력
    else:								# 제약사항에 해당하지 않는 경우
        print('#{} -1'.format(i))		# 테스트 케이스 번호와 오류메세지(-1)을 출력
        continue

모든 출처는 SW Expert 아카데미에 있습니다.

해당 글은 영리적 목적이 아닌 학습의 기록으로 사용되었습니다. 오기나 잘못된 부분은 말씀해주시면 수정하겠습니다.