[SWEA 1959번 / JAVA] 두 개의 숫자열

Question

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpoFaAS4DFAUq

SW Expert Academy

 

---

💡 Solution

배열의 길이가 더 큰 쪽을 기준으로 생각합니다. A 배열이 [1, 5, 3]이고 B 배열이 [3, 6, -7, 5, 4]라면 서로 마주보는 숫자들을 곱할 수 있는 경우는 [1 * 3, 5 * 6, 3 * -7],  [1 * 6, 5 * -7, 3 * 5], , [1 * -7, 5 * 5, 3 * 4] 총 3가지로 M - N + 1번입니다. 반대로 A 배열의 길이가 더 길다면 N - M + 1번의 경우의 수가 있습니다. 이 점을 활용하여 문제를 해결합니다.

 

 

💻 Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.security.Identity;
import java.util.StringTokenizer;

public class SWEA1959 {
	static int N, M;
	static int[] A;
	static int[] B;
	static int max;
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= 10; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			A = new int[N];
			B = new int[M];
			
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				A[i] = Integer.parseInt(st.nextToken());
			}
			
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < M; i++) {
				B[i] = Integer.parseInt(st.nextToken());
			}
			max = 0;
			solve();
			System.out.printf("#%d %d\n", tc, max);
		}

	}
	
	public static void solve() {	
		if (M > N) {
			for (int i = 0; i <= M - N; i++) {
				int idx = i;
				int sum = 0;
				for (int j = 0; j < N; j++) {
					sum += B[idx] * A[j];
					idx++;
				}
				if (sum > max) {
					max = sum;
				}
			}
		} else if (M < N){
			for (int i = 0; i <= N - M; i++) {
				int idx = i;
				int sum = 0;
				for (int j = 0; j < M; j++) {
					sum += A[idx] * B[j];
					idx++;
				}
				if (sum > max) {
					max = sum;
				}
			}	
		
		}
	}

}