[C++/백준] 2143 두 배열의 합

2143번: 두 배열의 합

 

[문제]

 

처음엔 좀 헷갈렸는데 예시랑 문제에서 봐야할 조건은 다음과 같다.

1. 합이 T가 되어야 한다.

2. 배열 A와 배열 B가 섞여 있어야 한다.

3. 한 배열에서 "구간"의 모든 수를 더해야 한다.

EX) i,j를 2,5 로 했을 경우 2~5를 모두 더해야 함. 2,5 이런식으로 떨어진 구간을 더하는 것이 불가능

 

---

[풀이 과정] 

처음엔 문제를 정확히 이해를 못해서 단순 조합에 백트래킹 같은거 섞어서 한다고 생각했다.

조건을 보면 N과 M의 최대가 1000개이기 때문에 완전 탐색으로는 불가능 하다는 사실을 알 수 있었다.

-> 2^1000 개많음. 2초 초과

 

다시 예제를 보니까 배열 구간의 연속하는 합 이라는 걸 확인할 수 있었고 거기서 누적합을 떠올렸다.

그럼 누적합을 구해서 어떻게 해야할까?  => 나올 수 있는 모든 숫자를 구해보자. 

예시 입력 ) 1 4 2 3

1

5

7

10

 

구해진 누적합에서 1~4, 2~4, 3~4, 4 이렇게 모든 경우를 구해보자는 생각이 들었다.

 

N의 개수, M의 개수를 최악의 경우 1000개이기 때문에 시간 복잡도를 계산해봐도 1+2+3+4.... 이런식으로 되니까 

1000*(1000+1)/2 로 50만 정도가 나와서 충분히 가능함.

 

이 숫자들(구간의 합 들)을 모두 numN, numM 이라는 배열에 각각 넣는다고 했을 때

T = numN[i] + numM[j] 라는 사실을 알 수 있다. 

 

그러면 numN에 들어있는 숫자를 기준으로 T - numN[i] = numM[j] 라는 수식을 알 수 있다.

numN을 기준으로 돌면서 numM에 해당하는 숫자가 있는지만 판별하면 된다 => vector / map(숫자/ 경우의 수)을 쓰자고 생각.

 

---

[코드]

 

1. 누적합을 구하고 vector에 넣어주는 작업까지 입력 단에서 한번에 처리

 

2. 가능한 경우의 수를 구해주는 과정

 

#include<iostream>
#include<map>
#include<vector>

using namespace std;

int T, N, M;
int sumN[1000]; // 누적합 n
int sumM[1000]; // 누적합 m

vector<long long> numN; // 나올 수 있는 모든 수를 넣은 n
map<long long, int> numM; // 나올 수 있는 모든 수와 경우의 수 m

int main() {
	cin >> T;
	cin >> N;

	sumN[0] = 0;
	sumM[0] = 0;
	
	for (int i = 1; i <= N; i++) {
		int n;
		cin >> n;
		sumN[i] = sumN[i - 1] + n;

		for (int j = 0; j < i; j++) {
			numN.push_back(sumN[i]-sumN[j]);
		}
	}

	cin >> M;
	
	for (int i = 1; i <= M; i++) {
		int m;
		cin >> m;
		sumM[i] = sumM[i - 1] + m;
		for (int j = 0; j < i; j++) {
			if (!numM[sumM[i] - sumM[j]]) {
				numM[sumM[i] - sumM[j]] = 1;
			}
			else {
				numM[sumM[i] - sumM[j]] += 1;
			}
		}
	}

	long long ans = 0;

	for (int i = 0; i < numN.size(); i++) {
		if (numM[T-numN[i]]) {
			ans += numM[T-numN[i]];
		}
	}

	cout << ans;

}

 

---

 

 [+ 추가]

 

여기서 자료형을 long long으로 해줬음. 

입력 원소의 절대값이 100만을 넘지 않는 정수인데, 진짜 최악을 가정해서 100만 * 1000이라고 치면 int 가뿐히 넘어버리는 상황이 발생할거라고 예상 됨 

 

 

++ 다른 블로그 참조해보면 틀은 비슷한데 vector를 그냥 사용해서 이분탐색으로 많이 풀었다.