2143 두 배열의 합

www.acmicpc.net/problem/2143

2143번: 두 배열의 합

#include<stdio.h>
#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
long long int N, M;//두배열 최대 입력
long long int T;// 찾아야하는 수
int A[1001], B[1001];//저장되는 배열
vector<int>sA;// A합
vector<int>sB;// B합
void init() {//초기화 및 초기 입력
	N = M = T = 0;
	memset(A, 0, sizeof(A));
	memset(B, 0, sizeof(B));
	scanf("%ld", &T);// 더해서 찾아지는 수
	scanf("%d", &N);// A의 개수
	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
	}
	scanf("%d", &M);// B의 개수
	for (int j = 0; j < M; j++) {
		scanf("%d", &B[j]);
	}
}
void preSum() {
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j < N-i; j++) {
			int sum = 0;
			for (int k = 0; k <=i; k++) {
				sum += A[j+k];
			}
			sA.push_back(sum);
		}
	}
	for (int i = 0; i <= M; i++) {
		for (int j = 0; j < M - i; j++) {
			int sum = 0;
			for (int k = 0; k <= i; k++) {
				sum += B[j + k];
			}
			sB.push_back(sum);
		}
	}
	sort(sA.begin(), sA.end());
	sort(sB.begin(), sB.end());
	int ret = 0;//최종 결과값
	for (int i = 0; i < sA.size(); i++) {
		for (int j = 0; j < sB.size(); j++) {
			if (sA[i] + sB[j] > T)break;
			if (sA[i] + sB[j] == T) {
				ret++;
			}
		} 
	}
	cout << ret << endl;
}
int main(void) {
	init();//초기화 및 초기 입력
	preSum();//미리 계산
	return 0;
}

일반적으로 N의 크기를 고려 하지 않았을때 이렇게 짜면 시간 초과가 납니다. 

#include<stdio.h>
#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
long long int N, M;//두배열 최대 입력
long long int T;// 찾아야하는 수
int A[1001], B[1001];//저장되는 배열
vector<int>sA;// A합
vector<int>sB;// B합
void init() {//초기화 및 초기 입력
	N = M = T = 0;
	memset(A, 0, sizeof(A));
	memset(B, 0, sizeof(B));
	scanf("%ld", &T);// 더해서 찾아지는 수
	scanf("%d", &N);// A의 개수
	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
	}
	scanf("%d", &M);// B의 개수
	for (int j = 0; j < M; j++) {
		scanf("%d", &B[j]);
	}
}
void preSum() {
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j < N-i; j++) {
			int sum = 0;
			for (int k = 0; k <=i; k++) {
				sum += A[j+k];
			}
			sA.push_back(sum);
		}
	}
	for (int i = 0; i <= M; i++) {
		for (int j = 0; j < M - i; j++) {
			int sum = 0;
			for (int k = 0; k <= i; k++) {
				sum += B[j + k];
			}
			sB.push_back(sum);
		}
	}
	sort(sA.begin(), sA.end());
	sort(sB.begin(), sB.end());
	long long int ret = 0;//최종 결과값
	for (int i = 0; i < sA.size(); i++) {
		long long int searchNum = T - sA[i];
		int low = lower_bound(sB.begin(), sB.end(),searchNum)-sB.begin();
		int high = upper_bound(sB.begin(), sB.end(), searchNum) - sB.begin();
		ret += (high - low);
	}
	cout << ret << endl;
}
int main(void) {
	init();//초기화 및 초기 입력
	preSum();//미리 계산
	return 0;
}

	for (int i = 0; i < sA.size(); i++) {
		long long int searchNum = T - sA[i];
		int low = lower_bound(sB.begin(), sB.end(),searchNum)-sB.begin();
		int high = upper_bound(sB.begin(), sB.end(), searchNum) - sB.begin();
		ret += (high - low);
	}
	cout << ret << endl;

이분탐색을 통한 알고리즘 기법을 활용하면 시간초과를 줄일 수 있고 빠르게 답을 찾을 수있습니다. 

 이런거 하나쯤 알아두면 좋겠죠?

저도 최근에 알게되서 ㅋㅋ 학습해서 이렇게 써먹어보네요.

 

예전의 저였으면 그냥 이런거 안풀었을 수도? ㅋㅋ