두 개의 숫자열 python,C++(SW Expert Academy)

난이도 : D2

문제번호 : 1959

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpoFaAS4DFAUq&categoryId=AV5PpoFaAS4DFAUq&categoryType=CODE

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

N 개의 숫자로 구성된 숫자열 Ai (i=1~N) 와 M 개의 숫자로 구성된 숫자열 Bj (j=1~M) 가 있다. Ai 나 Bj 를 자유롭게 움직여서 숫자들이 서로 마주보는 위치를 변경할 수 있다. 단, 더 긴 쪽의 양끝을 벗어나서는 안 된다. 서로 마주보는 숫자들을 곱한 뒤 모두 더할 때 최댓값을 구하라. 위 예제의 정답은 아래와 같이 30 이 된다.

제약사항

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

---

2. 문제풀이

배열을 입력받아 긴길이 - 짧은길이 만큼 쉬프트를 하며 곱한값중 제일높은값을 출력했습니다. 따라서 긴배열과 짧은 배열을 판단하는 로직과 길이의 차이만큼 옆으로 이동하며 더하는 로직을 만들었습니다.

 

---

3. 소스코드

def init():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    return N, M, A, B
 
 
def swap(A, B):
    if len(A) > len(B):
        return B, A
    return A, B
 
 
def calculate(A, B):
    maxNumber = float('-inf')
    diff = len(B) - len(A)
    for i in range(diff+1):
        tempNumber = 0
        for j in range(len(A)):
            tempNumber += A[j] * B[j+i]
        maxNumber = max(maxNumber, tempNumber)        
    return maxNumber
 
 
for t in range(int(input())):
    N, M, A, B = init()
    A, B = swap(A, B)
    answer = calculate(A, B)
    print('#{} {}'.format(t+1, answer))

 

#include <iostream>
#include <vector>
using namespace std;
//D2 1959 두개의 숫자열
int main() {
    //전체 반복횟수
    int len;
    cin >> len;
    for (int l = 1; l <= len; l++) {
        int a, b;
        long long max = 0;
        cin >> a >> b;
        vector<int> arr1(a), arr2(b), lo, sh;
        //a,b번만큼 반복하여 입력받기
        for (int i = 0; i < a; i++) cin >> arr1[i];
        for (int i = 0; i < b; i++)    cin >> arr2[i];
        //둘중 큰리스트를 찾아서 위치바꾸기
        if (arr1.size() >= arr2.size()) {
            lo = arr1;
            sh = arr2;
        }
        else {
            lo = arr2;
            sh = arr1;
        }
        //길이의 차이만큼 반복
        //옆으로 이동하면서 계산하며 제일 큰수를 찾는다.
        for (int i = 0; i <= lo.size() - sh.size(); i++) {
            long long temp = 0;
            for (int j = 0; j < sh.size(); j++) temp += lo[j + i] * sh[j];
            if (max < temp)    max = temp;
        }
        cout << "#" << l << " " << max << endl;
    }
    return 0;
}