[백준 2143] 두 배열의 합 - JAVA // le_effort//

문제를 읽고 쉽게 풀 줄 알았는데 삽질을 했다.

https://suhyeokeee.tistory.com/4

[백준 1208] 부분수열의 합2 자바// le_effot//

이 문제와 똑같이 접근하면 된다고 생각했었는데 여전히 나의 실력이 부족하다는 걸 느끼게 해 준 문제였다

일단 1208번 문제의 경우 "부분 수열" 이다

즉 {1,2,3} 이 있다면 올 수 있는 부분 수열은

{1} , {2} , {3}, {1,2} , {1,3} {2,3} {1,2,3} 이것처럼 원래 수열 안에 연속되어있지 않아도 가능하다

 

하지만 이 문제는 연속성이 있어야 한다

A = {1,3,1,2}

B = {1,3,2} 

T = 5 일 때

 

연속성이 없어도 된다면 (인덱스는 1부터 시작한다 가정) A[1]+A[4] +B[3] 을 하면

 A[1] = 1

 A[4] = 2

 B[3] = 2 

즉 5가 되는데 본문의 예시에서는 A[1]+A[4]+B[3]이 없다

 

1208번 처럼 

dfs(level+1, sum+arr[i]) 더해주고

dfs(level+1,sum) 안 더해주고

이렇게 접근을 했더니 풀릴 턱이 없었다

 

그리고 메모리 초과가 났는데 n이 1000까지 되니 이걸 다 재귀 호출하면서 나온 거라고 추정된다.

그래서 이번 문제의 부분합은

 

for(int i=0; i<n; i++) {
            int sum=0;
            for(int j=i; j<n;j++) {
                sum+=arr[j];
                a.add(sum);
            }
        }
        for(int i=0; i<m; i++) {
            int sum=0;
            for(int j=i; j<m;j++) {
                sum+=brr[j];
                b.add(sum);
            }
        }

이런 식으로 구현을 한다

n과 m 이 최대 1000 임으로 이중 반복문으로 해도 문제가 없다.

 

그다음은 1208번과 같은 로직으로 투 포인터 알고리즘으로 풀면 된다.

 

전체 코드

 

 

import java.io.*;
import java.util.*;
public class Main {
    static int t,n,m;
    static int arr[];
    static int brr[];
    static ArrayList<Integer> a = new ArrayList<>();
    static ArrayList<Integer> b = new ArrayList<>();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        t = Integer.parseInt(br.readLine());
        n = Integer.parseInt(br.readLine());
        String[] arr_input = br.readLine().split(" ");
        arr = new int [n];
        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(arr_input[i]);
        }
        
        m = Integer.parseInt(br.readLine());
        brr = new int[m];
        String[] brr_input = br.readLine().split(" ");
        for(int i=0; i<m; i++) {
            brr[i] = Integer.parseInt(brr_input[i]);
        }
        for(int i=0; i<n; i++) {
            int sum=0;
            for(int j=i; j<n;j++) {
                sum+=arr[j];
                a.add(sum);
            }
        }
        for(int i=0; i<m; i++) {
            int sum=0;
            for(int j=i; j<m;j++) {
                sum+=brr[j];
                b.add(sum);
            }
        }
        Collections.sort(a);
        Collections.sort(b);
        
        
        int a_idx=0;
        int b_idx= b.size()-1;
        long cnt = 0;
        while(a_idx<a.size() &&b_idx>=0) {
            
            int a_sum = a.get(a_idx);
            int b_sum = b.get(b_idx);
            long a_cnt =0;
            long b_cnt =0;
            if(a_sum+b_sum==t) {
                while(a_idx<a.size() && a.get(a_idx)==a_sum) {
                    a_idx++;
                    a_cnt++;
                }
                while(b_idx>=0 && b.get(b_idx)==b_sum) {
                    b_idx--;
                    b_cnt++;
                }
                cnt+=a_cnt*b_cnt;
            }
            if(a_sum+b_sum>t) {
                b_idx--;
            }
            if(a_sum+b_sum<t) {
                a_idx++;
            }
        }
        System.out.println(cnt);
    }
}