설명
고객이 두 종류의 피자 A와 B를 취급하는 피자가게에서 피자를 주문하고자 한다. <그림 1>과 같이 각 종류의 피자는 다양한 크기의 여러 개의 피자조각으로 나누어져 있다. 각 조각에 쓰여진 숫자는 피자조각의 크기를 나타낸다.
<그림 1>
고객이 원하는 피자의 크기를 이야기하면, 피자가게에서는 한 종류의 피자를 2 조각 이상 판매할 때는 반드시 연속된 조각들을 잘라서 판매한다. 이때 판매한 피자조각의 크기 합이 주문한 크기가 되어야 한다. 판매한 피자조각은 모두 A종류이거나, 모두 B종류이거나, 또는 A와 B 종류가 혼합될 수 있다. 예를 들어서, <그림 1> 과 같이 잘라진 피자가 있을 때, 손님이 전체 크기가 7 인 피자를 주문하면, 피자 가게에서는 <그림2>와 같이 5 가지 방법으로 피자를 판매할 수 있다.
<그림 2>
피자가게에서 손님이 원하는 크기의 피자를 판매하는 모든 방법의 가지 수를 계산하는 프로그램을 작성하시오
입력
첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n ≤ 1000). 세 번째 줄부터 차례로 m 개의 줄에는 피자 A의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 그 다음 n 개의 줄에는 차례로 피자B의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 각 종류의 피자조각의 크기는 시계방향으로 차례로 주어지며, 각 피자 조각의 크기는 1000 이하의 자연수이다.
출력
첫째 줄에는 피자를 판매하는 방법의 가지 수를 나타내는 정수를 출력한다. 피자를 판매하는 방법이 없는 경우에는 숫자 0을 출력한다.
예시 입력
예시 출력
7
5 3
2
2
1
7
2
6
8
3
JavaScript
복사
5
JavaScript
복사
풀이 과정
이게 골드 2?
최종 코드
package baekjoon.binary_search;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;
public class _2632 {
static HashMap<Integer, Integer> aPizzaMap = new HashMap<>();
static HashMap<Integer, Integer> bPizzaMap = new HashMap<>();
static int size;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
size = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int[] aPizza = new int[A];
int[] bPizza = new int[B];
for (int i = 0; i < A; i++) {
aPizza[i] = Integer.parseInt(br.readLine());
}
for (int i = 0; i < B; i++) {
bPizza[i] = Integer.parseInt(br.readLine());
}
calculatePizzaCombination(aPizza, aPizzaMap);
calculatePizzaCombination(bPizza, bPizzaMap);
int answer = aPizzaMap.getOrDefault(size, 0) + bPizzaMap.getOrDefault(size, 0);
for (int a : aPizzaMap.keySet()) {
if (bPizzaMap.containsKey(size - a)) {
answer += aPizzaMap.get(a) * bPizzaMap.get(size - a);
}
}
System.out.println(answer);
}
private static void calculatePizzaCombination(int[] pizza, HashMap<Integer, Integer> pizzaMap) {
int totalSum = 0;
for (int slice : pizza) {
totalSum += slice;
}
for (int start = 0; start < pizza.length; start++) {
int sum = 0;
for (int end = 1; end < pizza.length; end++) {
sum += pizza[(start + end) % pizza.length];
if (sum > size) {
break;
}
pizzaMap.put(sum, pizzaMap.getOrDefault(sum, 0) + 1);
}
}
if (totalSum <= size) {
pizzaMap.put(totalSum, pizzaMap.getOrDefault(totalSum, 0) + 1);
}
}
}
JavaScript
복사
