[Java] SWEA 1959번: 두 개의 숫자열

문제

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

---

일단 이해하자🤔

• Ai나 Bj 중 어떤 배열이 크든 큰 배열의 크기를 벗어날 수 없으므로 N과 M의 대소를 가린 뒤 (같을 경우 어디든 상관없다), 이중 for문을 사용하여 i는 N - M번 혹은 M - N번 반복하고 j는 N과 M 중 더 작은 값만큼 반복한다.
• 배열을 곱할 때, 인덱스 값이 중요한데 만약 N이 M보다 클 경우, Ai[j + i]과 Bj[j]를 곱해야한다. 왜냐하면 i는 0부터 N - M까지, j는 0부터 M - 1까지므로 Ai는 0~M-1, 1~M, ... , N-M~N와 같은 구간으로 N-M번 곱해져야하기 때문이다.

---

👀 풀이

import java.util.Scanner;
 
class Solution
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();
 
        for(int test_case = 1; test_case <= T; test_case++)
        {
            int N = sc.nextInt();
            int M = sc.nextInt();
            int Ai[] = new int[N];
            int Bj[] = new int[M];
            int maxSum = 0;
            int sum;
 
            for (int i = 0; i < N; i++) {
                Ai[i] = sc.nextInt();
            }
 
            for (int i = 0; i < M; i++) {
                Bj[i] = sc.nextInt();
            }
 
            if (N > M) {
                for (int i = 0; i < N - M + 1; i++) {
                    sum = 0;
                    for (int j = 0; j < M; j++) {
                        sum += Ai[j + i] * Bj[j];
                    }
                    if (maxSum < sum) {
                        maxSum = sum;
                    }
                }
            }
 
            else {
                for (int i = 0; i < M - N + 1; i++) {
                    sum = 0;
                    for (int j = 0; j < N; j++) {
                        sum += Ai[j] * Bj[j + i];
                    }
                    if (maxSum < sum) {
                        maxSum = sum;
                    }
                }
            }
 
 
            System.out.println("#" + test_case + " " + maxSum);
        }
    }
}