[SWEA] 1959. 두 개의 숫자열

문제

N 개의 숫자로 구성된 숫자열 Ai (i=1~N) 와 M 개의 숫자로 구성된 숫자열 Bj (j=1~M) 가 주어졌을 때,

각 원소 값의 곱이 최대가 되는 값을 구하는 문제

 

예를 들어,

A = [1, 2, 3]

B = [3, 4, 5, 6, 7]

가 주어졌을 때,

 

case 1)

[1, 2, 3] * [3, 4, 5] 

(1 * 3) + (2 * 4) + (3 * 5) = 26

 

case 2)

[1, 2, 3] * [4, 5, 6]

(1 * 4) + (2 * 5) + (3 * 6) = 32

 

case 3)

[1, 2, 3] * [5, 6, 7]

(1 * 5) + (2 * 6) + (3 * 7) = 38

 

최대값은 38이 된다.

 

풀이방법

1) 입력된 두 배열 중 길이가 짧은 배열을 구한다

 

2) 길이가 긴 배열의 인덱스를 하나씩 늘려가며 길이가 짧은 배열의 원소와의 합을 구한다

 

3) 최대값을 찾는다.

 

소스코드

package samsung;

import java.util.*;

public class s_1959 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int test = sc.nextInt();
		
		for(int t = 1; t <= test; t++) {
			int n1 = sc.nextInt();
			int n2 = sc.nextInt();
			int[] a1 = new int[n1];
			int[] a2 = new int[n2];
			int max = 0;
			
			for(int i = 0; i < n1; i++) {
				a1[i] = sc.nextInt();
			}
			
			for(int i = 0; i < n2; i++) {
				a2[i] = sc.nextInt();
			}
			
			if(n1 > n2) {
				for(int i = 0; i < n1 - n2 + 1; i++) {
					int sum = 0;
					for(int j = 0; j < n2; j++) {
						sum += a2[j] * a1[i+j];
					}
					max = Math.max(sum, max);
				}
			}
			else {
				for(int i = 0; i < n2 - n1 + 1; i++) {
					int sum = 0;
					for(int j = 0; j < n1; j++) {
						sum += a1[j] * a2[i+j];
					}
					max = Math.max(sum, max);
				}
			}
			System.out.println("#" + t + " " + max);
		}
	}
}