📝 문제

📌 풀이

1. 피자 a, b에 대해서 조각을 선택하여 나올 수 있는 피자 크기의 모든 경우의 수를 배열로 만든다.

• deque를 통해 실제로 배열의 앞에 있는 값을 뒤로 보낸 후 누적합을 통해 구한다.
• 모든 피자 조각을 선택하는 경우는 한번만 추가되도록 한다.

2. 모든 경우의 수 배열을 오름차순 정렬한다.
3. 원하는 크기의 피자를 만들기 위한 피자 a, 피자 b 조각의 크기 조합을 찾는다.

• 예를 들면 크기 7의 피자를 원하면 (0, 7), (1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1), (7, 0)의 조각을 갖도록 하는 피자 a와 b의 경우를 찾고 곱한다.
• 경우의 개수를 세는 방법은 각 피자에서 나올 수 있는 모든 경우의 수에서 찾는 수의 upper_bound - lower_bound를 하면 배열 안에 있는 찾는 수의 개수를 구할 수 있다.

⭐ deque를 활용하여 실제로 배열을 수정하여 모든 경우의 수를 구했지만 인덱스 선택을 %로 조절하여 바로 구할 수도 있다.

💻 코드

//난이도 : 골드2
//시작 : 
//끝 :
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;

// arr 피자로 만들 수 있는 모든 경우의 수 찾는 함수
deque<int> make_case(deque<int> arr) {
	deque<int> all_case;
	
	for (int i = 0; i < arr.size(); i++) {
		int sum = 0;
		for (int j = 0; j < arr.size() - 1; j++) {  // 모든 조각을 고른 경우는 마지막에 한번만 수행
			sum += arr[j];  // 누적합을 통해 경우의 수 생성
			all_case.push_back(sum);
		}
		int tmp = arr.front(); //앞쪽 조각을 뒤로 옮기면서 반복
		arr.pop_front();
		arr.push_back(tmp);
	}
	int sum = 0; //select all pizza pieces
	for (int j = 0; j < arr.size(); j++) {
		sum += arr[j];
	}
	all_case.push_back(sum);

	//for (int i = 0; i < all_case.size(); i++) {
	//	cout << all_case[i] << " ";
	//}

	return all_case;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	deque<int> pizza_a;
	deque<int> pizza_b;
	int pizza_size;
	cin >> pizza_size;
	int m, n;
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		int tmp;
		cin >> tmp;
		pizza_a.push_back(tmp);
	}
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		pizza_b.push_back(tmp);
	}

	deque<int> pizza_a_case = make_case(pizza_a);
	sort(pizza_a_case.begin(), pizza_a_case.end());  // 이분 탐색을 위해 정렬
	deque<int> pizza_b_case = make_case(pizza_b);
	sort(pizza_b_case.begin(), pizza_b_case.end());  // 이분 탐색을 위해 정렬

	int result = 0;
	for (int i = 1; i < pizza_size; i++) {
		int pizza_a_size = i;
		int pizza_b_size = pizza_size - pizza_a_size;

		int a_upper = upper_bound(pizza_a_case.begin(), pizza_a_case.end(), pizza_a_size) - pizza_a_case.begin();
		int a_lower = lower_bound(pizza_a_case.begin(), pizza_a_case.end(), pizza_a_size) - pizza_a_case.begin();
		int a_case = a_upper - a_lower;  // 찾는 조각 크기의 개수

		int b_upper = upper_bound(pizza_b_case.begin(), pizza_b_case.end(), pizza_b_size) - pizza_b_case.begin();
		int b_lower = lower_bound(pizza_b_case.begin(), pizza_b_case.end(), pizza_b_size) - pizza_b_case.begin();
		int b_case = b_upper - b_lower;  // 찾는 조각 크기의 개수

		result += a_case * b_case;  // 조합이기 때문에 곱
	}
	// 하나의 피자로만 조건을 만족하는 경우
	int a_upper = upper_bound(pizza_a_case.begin(), pizza_a_case.end(), pizza_size) - pizza_a_case.begin();
	int a_lower = lower_bound(pizza_a_case.begin(), pizza_a_case.end(), pizza_size) - pizza_a_case.begin();
	result += a_upper - a_lower;  

	int b_upper = upper_bound(pizza_b_case.begin(), pizza_b_case.end(), pizza_size) - pizza_b_case.begin();
	int b_lower = lower_bound(pizza_b_case.begin(), pizza_b_case.end(), pizza_size) - pizza_b_case.begin();
	result += b_upper - b_lower;

	cout << result << '\n';



	return 0;
}