시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 2731 | 1034 | 676 | 35.900% |
문제
고객이 두 종류의 피자 A와 B를 취급하는 피자가게에서 피자를 주문하고자 한다. <그림 1>과 같이 각 종류의 피자는 다양한 크기의 여러 개의 피자조각으로 나누어져 있다. 각 조각에 쓰여진 숫자는 피자조각의 크기를 나타낸다.
고객이 원하는 피자의 크기를 이야기하면, 피자가게에서는 한 종류의 피자를 2 조각 이상 판매할 때는 반드시 연속된 조각들을 잘라서 판매한다. 이때 판매한 피자조각의 크기 합이 주문한 크기가 되어야 한다. 판매한 피자조각은 모두 A종류이거나, 모두 B종류이거나, 또는 A와 B 종류가 혼합될 수 있다. 예를 들어서, <그림 1> 과 같이 잘라진 피자가 있을 때, 손님이 전체 크기가 7 인 피자를 주문하면, 피자 가게에서는 <그림2>와 같이 5 가지 방법으로 피자를 판매할 수 있다.
피자가게에서 손님이 원하는 크기의 피자를 판매하는 모든 방법의 가지 수를 계산하는 프로그램을 작성하시오
입력
첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n ≤ 1000). 세 번째 줄부터 차례로 m 개의 줄에는 피자 A의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 그 다음 n 개의 줄에는 차례로 피자B의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 각 종류의 피자조각의 크기는 시계방향으로 차례로 주어지며, 각 피자 조각의 크기는 1000 이하의 자연수이다.
출력
첫째 줄에는 피자를 판매하는 방법의 가지 수를 나타내는 정수를 출력한다. 피자를 판매하는 방법이 없는 경우에는 숫자 0을 출력한다.
예제 입력 1
7
5 3
2
2
1
7
2
6
8
3
예제 출력 1
5
코드
import java.io.*;
import java.util.*;
public class p2632 {
static int k;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
k = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
int[] arr1 = new int[m];
int[] arr2 = new int[n];
for (int i = 0; i < m; i++) {
arr1[i] = Integer.parseInt(br.readLine());
}
for (int i = 0; i < n; i++) {
arr2[i] = Integer.parseInt(br.readLine());
}
List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new ArrayList<>();
// 투포인터 활용해서 부분합 리스트 생성
int lo = 0;
int hi = 0;
int sum = 0;
while (lo < arr1.length) {
sum += arr1[hi++];
if (sum <= k) {
list1.add(sum);
} else {
lo++;
hi = lo;
sum = 0;
}
hi = hi % m;
if ((lo == 0 && hi== 0) || hi + 1 == lo) {
lo++;
hi = lo;
sum = 0;
}
}
lo = 0;
hi = 0;
sum = 0;
while (lo < arr2.length) {
sum += arr2[hi++];
if (sum <= k) {
list2.add(sum);
} else {
lo++;
hi = lo;
sum = 0;
}
hi = hi % n;
if ((lo == 0 && hi== 0) || hi + 1 == lo) {
lo++;
hi = lo;
sum = 0;
}
}
Collections.sort(list1);
Collections.sort(list2);
int result = 0;
int left = 0;
int right = list2.size() - 1;
// 모든 부분합의 경우의 수를 다 돌면서 확인한다.
while (left < list1.size() && right >= 0) {
int left_val = list1.get(left);
int right_val = list2.get(right);
// 목표값 위치
if (left_val + right_val == k) {
int left_cnt = 0;
int right_cnt = 0;
while (left < list1.size() && list1.get(left) == left_val) {
left_cnt++;
left++;
}
while (right >= 0 && list2.get(right) == right_val) {
right_cnt++;
right--;
}
result += left_cnt * right_cnt;
}
// 목표값을 향해서 포인터 한칸씩 이동
if (left_val + right_val < k) {
left++;
}
if (left_val + right_val > k) {
right--;
}
}
// left or right 한쪽 포인터가 범위 밖으로 나갔을 경우
for (int i = 0; i < list1.size(); i++) {
if (list1.get(i) == k) {
result++;
}
}
for (int i = 0; i < list2.size(); i++) {
if (list2.get(i) == k) {
result++;
}
}
System.out.println(result);
}
}
'알고리즘 > [ Baekjoon ]' 카테고리의 다른 글
[ BOJ ][JAVA][2667] 단지번호붙이기 (0) | 2021.04.24 |
---|---|
[ BOJ ][JAVA][2661] 좋은수열 (0) | 2021.04.24 |
[ BOJ ][JAVA][2615] 오목 (2) | 2021.04.24 |
[ BOJ ][JAVA][2609] 최대공약수와 최소공배수 (0) | 2021.04.24 |
[ BOJ ][JAVA][2580] 스도쿠 (0) | 2021.04.24 |