문제 링크입니다: https://www.acmicpc.net/problem/2632
N과 M이 최대 1000이기 때문에 미리 시간복잡도 O(N^2)으로 전처리해도 무방한 문제였습니다.
알고리즘은 아래와 같습니다.
1. 모든 가능한 합을 미리 v와 v2에 전처리 해줍니다.
2. v[i]에 대해 lower_bound와 upper_bound를 이용하여 v2에 (pizza - v[i])가 몇개 있는지 확인하고 결과에 더해줍니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int pizza;
cin >> pizza;
int M, N;
cin >> M >> N;
vector<int> A(M), B(N);
for (int i = 0; i < M; i++)
cin >> A[i];
for (int i = 0; i < N; i++)
cin >> B[i];
//전처리
vector<int> v(1, 0), v2(1, 0);
int low = 0, high = 0;
int sum = 0;
while (low < A.size())
{
sum += A[high++];
if (sum <= pizza)
v.push_back(sum);
else
{
low++;
high = low;
sum = 0;
}
//원형 배열
if (high == A.size())
high = 0;
//전체 다 더한 값 중복 방지
if ((!low && !high) || high + 1 == low)
{
low++;
high = low;
sum = 0;
}
}
low = 0, high = 0, sum = 0;
while (low < B.size())
{
sum += B[high++];
if (sum <= pizza)
v2.push_back(sum);
else
{
low++;
high = low;
sum = 0;
}
//원형 배열
if (high == B.size())
high = 0;
//전체 다 더한 값 중복 방지
if ((!low && !high) || high + 1 == low)
{
low++;
high = low;
sum = 0;
}
}
sort(v.begin(), v.end());
sort(v2.begin(), v2.end());
int result = 0;
for (int i = 0; i < v.size(); i++)
{
int low = lower_bound(v2.begin(), v2.end(), pizza - v[i]) - v2.begin();
int high = upper_bound(v2.begin(), v2.end(), pizza - v[i]) - v2.begin();
result += high - low;
}
cout << result << "\n";
return 0;
}
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
백준 14614번 Calculate! (0) | 2019.01.29 |
---|---|
백준 2143번 두 배열의 합 (0) | 2019.01.27 |
백준 3020번 개똥벌레 (8) | 2019.01.27 |
백준 7453번 합이 0인 네 정수 (3) | 2019.01.27 |
백준 1208번 부분집합의 합 2 (6) | 2019.01.27 |