-
https://www.acmicpc.net/problem/2632
아이디어
vector<int> pizzaA; vector<int> pizzaB; //A에서 나올 수 있는 합 vector<int> cntA; //B에서 나올 수 있는 합 vector<int> cntB; int n; void input() { cin >> n; cin >> a >> b; pizzaA.resize(a+1); pizzaB.resize(b+1); for (int i = 0; i < a; i++) { cin >> pizzaA[i]; } for (int i = 0; i < b; i++) { cin >> pizzaB[i]; } cntA.resize(2000001); cntB.resize(2000001); } void func(int p, vector<int> &arr, vector<int> &arrCnt) { //뒤로 늘려감 for (int i = 1; i <= p; i++) { int sum = 0; for (int j = 0; j < i; j++) { sum += arr[j]; } arrCnt[sum]++; //피자 하나에서만 가져오는 케이스 if (sum == n) cnt++; if (i == p) break; //앞에서 줄여감 for (int j = 1; j < p; j++) { sum -= arr[j - 1]; sum += arr[(j + i - 1) % p]; arrCnt[sum]++; //피자 하나에서만 가져오는 케이스 if (sum == n) cnt++; } } } void solution() { // a에서의 연속된 피자의 합 func(a, pizzaA, cntA); // b에서의 연속된 피자의 합 func(b, pizzaB, cntB); for (int i = 1; i < n; i++) { int j = n - i; cnt += cntA[i] * cntB[j]; } cout << cnt; } int main(void) { input(); solution(); }
'알고리즘 > 백준' 카테고리의 다른 글
BOJ 1939 중량제한 / C++ (0) 2022.12.03 BOJ 18428 감시 피하기 / C++ (0) 2022.12.03 BOJ 3109 빵집 / C++ (2) 2022.09.15 BOJ 1322 X와 K / C++ (0) 2022.09.15 BOJ 2096 내려가기 / C++ (0) 2022.09.11 댓글