문제 출처
https://www.acmicpc.net/problem/2632
2632번: 피자판매
첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 ( 3≤m, n≤1000). 세 번째 줄부터 차례로 m 개의 줄에는 피자 A의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 그 다음 n 개의 줄에는 차례로 피자B의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 각 종류의 피자조각의 크기
www.acmicpc.net
접근 방식 및 풀이
- A피자, B피자의 부분합의 배열을 구한다.
- 두 부분합의 배열을 투포인트 알고리즘을 통해 목표값을 찾는다.
- 참고블로그
소스 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main {
static int target;
static int m;
static int n;
static int[] A;
static int[] B;
static boolean[] check;
static ArrayList<Integer> AList = new ArrayList<>();
static ArrayList<Integer> BList = new ArrayList<>();
static int ans=0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
target = sc.nextInt();
m = sc.nextInt();
n = sc.nextInt();
A=new int[m];
B=new int[n];
for (int i = 0; i <m ; i++) {
A[i] = sc.nextInt();
}
for (int i = 0; i <n ; i++) {
B[i] = sc.nextInt();
}
//A 피자에 대한 부분합 만들기
for (int i = 0; i <m ; i++) {
check = new boolean[m];
check[i]=true;
getSum(A[i], i, i+1, check, A, AList);
}
//B 피자에 대한 부분합 만들기
for (int i = 0; i <n ; i++) {
check = new boolean[n];
check[i]=true;
getSum(B[i], i, i+1, check, B, BList);
}
AList.add(0);
BList.add(0);
Collections.sort(AList);
Collections.sort(BList);
int leftIdx= 0;
int rightIdx = BList.size() -1;
while(leftIdx < AList.size() && rightIdx >=0){//두 배열 사이즈 안에서 실행
// left, right index의 value 가져옴.
int lv = AList.get(leftIdx);
int rv = BList.get(rightIdx);
if(lv+rv ==target){// 목표값이 등장했으므로
int lc =0;
int rc = 0;
while (leftIdx < AList.size() && AList.get(leftIdx) == lv){
lc++;
leftIdx++;
}
while (rightIdx >=0 && BList.get(rightIdx) == rv){
rc++;
rightIdx--;
}
ans += lc*rc;
}
if(lv+rv > target) rightIdx--;
if(lv+rv < target) leftIdx++;
}
System.out.println(ans);
}
private static void getSum(int sum, int startIdx, int idx, boolean[] check, int[] arr, ArrayList<Integer> list) {
if(idx == arr.length){
idx = 0;
}
list.add(sum);
// 아직 안담은 피자 조건에대해서만 && 순환 방지함.
if(check[idx] == false && sum <= target && idx != startIdx-1){
check[idx] =true;
getSum(sum+arr[idx] , startIdx, idx +1, check, arr,list);
}else {
return;
}
}
}
|
결과
'Competition > Baekjoon' 카테고리의 다른 글
| [백준] 3108번 자바 로고 (0) | 2020.05.10 |
|---|---|
| [백준] 2580번 자바 스도쿠 (0) | 2020.05.10 |
| [백준] 9095번 자바 1,2,3 더하기 (0) | 2020.05.08 |