[java]두 개의 숫자열 - SWEA 1959

풀이

문제 해석을 하자면,

• 마주본 두개의 문자열의 곱의 합이 제일 큰 값을 도출하라

풀이

• 숫자열은 연속되어 있다.
• 더 짧은 숫자열이 A라 가정하면, B의 처음부터 끝자리까지 움직이면서 최대값을 구하자
  • 물론, A와 B가 숫자열이 같을수도 있으니 이러한 상황도 전부 고려하자
  • Index만 잘 계산해주면 되는 문제이다.
• 예상 복잡도는 O(NM)

코드

import java.io.*;
import java.util.*;
public class 두개의숫자열_1959 {
  public static long[] A = new long[22];
  public static long[] B = new long[22];

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    int T = Integer.parseInt(br.readLine());
    for(int t=1; t<=T; t++) {
      //init
      for(int i=0; i<22; i++) {
        A[i] = 0;
        B[i] = 0;
      }
      //input
      StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
      int N = Integer.parseInt(stk.nextToken());
      int M = Integer.parseInt(stk.nextToken());
      stk = new StringTokenizer(br.readLine(), " ");
      for(int i=0; i<N; i++)  A[i]=Integer.parseInt(stk.nextToken());
      stk = new StringTokenizer(br.readLine(), " ");
      for(int i=0; i<M; i++)  B[i]=Integer.parseInt(stk.nextToken());
      //run
      long result = 0;
      if(N<=M) { // N<M 과 N==M
        int copyN = N;
        do { // M-N==0 도 계산위해 do-while 사용
          long temp = 0;
          int diff = M-copyN;
          for(int i=0; i<N; i++) {
            temp += A[i]*B[diff+i]; // calculate
          }
          result = Math.max(result, temp);
          copyN++;
        }while(M-copyN!=-1);
      } else { // N>M
        int copyM = M;
        while(N-copyM!=-1) {
          long temp = 0;
          int diff = N-copyM;
          for(int i=0; i<M; i++) {
            temp += A[diff+i]*B[i]; // calculate
          }
          result = Math.max(result, temp);
          copyM++;
        }
      }
      //output
      sb.append("#"+t+" "+result+"\n");
    }
    System.out.print(sb);
  }
}

느낀점

생략