2143 (두 배열의 합, 중요)

두 배열의 합 : https://www.acmicpc.net/problem/2143

 

 

일반적인 부분배열로 생각하고 풀었는데 답이 크게 나왔다.

 

문제를 다시 확인하니, 연속된 부분합이다.

경우의 수를 놓고 계산을 해보니, 부분합의 개수는 N(N+1)/2 이다.

 

여러문제를 겪어보니 가장 번거로운 점이 부분합의 배열을 만드는 것이다.

인덱스와 for문 만드는 연습이 필요하다.

 

2-point 알고리즘은 이제 특별할 것이 없다.

중복이 나오는 경우만 잘 체크해주면 항상 같은 형태이다.

 

//case 1 부분합을 int array로 구현한 case

//수행속도 약 440ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static int N, M, T;

	static int[] a, b;
	static int[] aa, bb;
	static int aIdx = 0, bIdx = 0;
	static boolean DBG = false;
	static int answer = 0;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		T = Integer.parseInt(st.nextToken());

		N = Integer.parseInt(br.readLine());
		a = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++)
			a[i] = Integer.parseInt(st.nextToken());

		M = Integer.parseInt(br.readLine());
		b = new int[M];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++)
			b[i] = Integer.parseInt(st.nextToken());

		aa = new int[(N * (N + 1)) / 2  ];
		for (int i = 0; i < a.length; i++) {
			int sum = 0;			
			for (int j = i; j < a.length; j++) {				
				sum += a[j];
				if (DBG)
				System.out.printf("[%d %d]sum : %d\n", i,j,sum);
				aa[aIdx++] = sum;
			}
		}
		bb = new int[(M * (M + 1)) / 2  ];
		for (int i = 0; i < b.length ; i++) {
			int sum = 0;			
			for (int j = i; j < b.length; j++) {  
				sum += b[j];
				bb[bIdx++] = sum;
			}
		}

		Arrays.sort(aa);
		Arrays.sort(bb);

		if (DBG)
		{
			System.out.println("aa:");
			for (int v : aa)
				System.out.print(v + " ");
			System.out.println();

			System.out.println("bb:");
			for (int v : bb)
				System.out.print(v + " ");
			System.out.println();
		}

		// aa and bb 의 부분합이므로 aa or bb only는 count하지 않는다.

		int aap = 0;
		int bbp = bb.length - 1;
		long cnt = 0;
		while (aap < aa.length && bbp > -1) {

			long aav = aa[aap];
			long bbv = bb[bbp];
			long sum = aav + bbv;

			if (sum > T) {
				bbp--;
			} else if (sum < T) {
				aap++;
			} else {
				long aaCnt = 0, bbCnt = 0;
				while (aap < aa.length && aav == aa[aap]) {
					aap++;
					aaCnt++;
				}

				while (bbp > -1 && bbv == bb[bbp]) {
					bbp--;
					bbCnt++;
				}
				cnt += aaCnt * bbCnt;
				if (DBG)
				System.out.printf("cnt : %d [ %d %d ]aaCnt: %d  bbCnt %d\n", cnt, aav, bbv, aaCnt, bbCnt);
			}
		}

		System.out.println(cnt);
	}

}

 

 

//case2 : 부분합을 ArrayList로 구현한 case로, 부분합의 length를 신경 쓸 필요 없다는 점이 장점. 

수행시간 약 880ms 

참조 :https://lotuslee.tistory.com/31

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static int N, M, T;

	static int[] a, b;
	static boolean DBG = false;
	static int answer = 0;
	static ArrayList<Integer> listA = new ArrayList<>();
	static ArrayList<Integer> listB = new ArrayList<>();
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		T = Integer.parseInt(st.nextToken());

		N = Integer.parseInt(br.readLine());
		a = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++)
			a[i] = Integer.parseInt(st.nextToken());

		M = Integer.parseInt(br.readLine());
		b = new int[M];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++)
			b[i] = Integer.parseInt(st.nextToken());

		for (int i = 0; i < a.length; i++) {
			int sum = 0;			
			for (int j = i; j < a.length; j++) {				
				sum += a[j];
				if (DBG)
				System.out.printf("[%d %d]sum : %d\n", i,j,sum);
				listA.add(sum);
			}
		}
		for (int i = 0; i < b.length ; i++) {
			int sum = 0;			
			for (int j = i; j < b.length; j++) {  
				sum += b[j];
				listB.add(sum);
			}
		}

		Collections.sort(listA);
		Collections.sort(listB);
		
		
		if (DBG)
		{
			System.out.println("listA:");
			for (int v : listA)
				System.out.print(v + " ");
			System.out.println();

			System.out.println("listB:");
			for (int v : listB)
				System.out.print(v + " ");
			System.out.println();
		}

		// aa and bb 의 부분합이므로 aa or bb only는 count하지 않는다.

		int aap = 0;
		int bbp = listB.size()-1;
		long cnt = 0;
		while (aap < listA.size() && bbp > -1) {

			long aav = listA.get(aap);
			long bbv = listB.get(bbp);
			long sum = aav + bbv;

			if (sum > T) {
				bbp--;
			} else if (sum < T) {
				aap++;
			} else {
				long aaCnt = 0, bbCnt = 0;
				while (aap < listA.size() && aav == listA.get(aap)) {
					aap++;
					aaCnt++;
				}

				while (bbp > -1 && bbv == listB.get(bbp)) {
					bbp--;
					bbCnt++;
				}
				cnt += aaCnt * bbCnt;
				if (DBG)
				System.out.printf("cnt : %d [ %d %d ]aaCnt: %d  bbCnt %d\n", cnt, aav, bbv, aaCnt, bbCnt);
			}
		}

		System.out.println(cnt);
	}

}