https://www.acmicpc.net/problem/2632
2632번: 피자판매
첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n
www.acmicpc.net
코드
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
#include < iostream>
#include < vector >
#include < algorithm>
using namespace std ;
int main() {
ios::sync_with_stdio(false );
cin .tie(NULL );
int pizza;
int m,n;
cin > > pizza> > m> > n;
int a[m];
int b[n];
for (int i= 0 ;i< m;i+ + )
{
cin > > a[i];
}
for (int i= 0 ;i< n;i+ + )
{
cin > > b[i];
}
vector < int > apizza;
vector < int > bpizza;
int tt= 0 ;
for (int i= 0 ;i< m;i+ + )
{
if (a[i]< = pizza)
{
apizza.push_back (a[i]);
int j= i+ 1 ;
if (j= = m)j= 0 ;
int sum= a[i];
while (sum< = pizza & & i! = j)
{
sum+ = a[j];
if (sum< = pizza)apizza.push_back (sum);
else break ;
j+ + ;
if (j= = m)j= 0 ;
if (i= = j & & tt= = 1 )
{
apizza.pop_back();
}
if (i= = j & & tt= = 0 )
{
tt= 1 ;
}
}
}
}
tt= 0 ;
for (int i= 0 ;i< n;i+ + )
{
if (b[i]< = pizza)
{
bpizza.push_back (b[i]);
int j= i+ 1 ;
if (j= = n)j= 0 ;
int sum= b[i];
while (sum< = pizza & & i! = j)
{
sum+ = b[j];
if (sum< = pizza)bpizza.push_back (sum);
else break ;
j+ + ;
if (j= = n)j= 0 ;
if (i= = j & & tt= = 1 )
{
bpizza.pop_back();
}
if (i= = j & & tt= = 0 )
{
tt= 1 ;
}
}
}
}
apizza.push_back (0 );
bpizza.push_back (0 );
sort(apizza.begin (),apizza.end ());
sort(bpizza.begin (),bpizza.end ());
int res= 0 ;
for (int i= 0 ;i< apizza.size ();i+ + )
{
res+ = upper_bound(bpizza.begin (),bpizza.end (),pizza- apizza[i])- lower_bound(bpizza.begin (),bpizza.end (),pizza- apizza[i]);
}
cout < < res;
return 0 ;
}
cs
풀이
24행부터 50행, 51행부터 77행에서 A, B 피자를 한 종류의 피자를 2조각 이상 판매할 때는 반드시 연속된 조각들을 잘라서 판매한다는 규칙을 지켜서 자를 수 있는 모든 경우의 수의 잘린 피자의 크기의 합을 벡터에 넣어준다. 원형배열처럼 동작하도록 만들기 위해 31행의 if(j==m)j=0; 등의 코드가 들어간다. 여기서 주의해야 할 점은 한 피자의 모든 조각의 크기를 합친 값이 손님이 구매하고자 하는 피자 크기 보다 작아서 모든 조각을 판매하는 경우에는 1가지 경우이다. (1번 조각부터 n번 조각 까지 자르든 2번부터 3번 4 번 ,,, n번 1번 조각까지 자르든 똑같은 경우이다) 이를 위해서 40~47행의 코드가 필요하다.
그 후에 하나의 피자에서 구매하고자 하는 피자 크기를 다 채울 수 있는 경우를 처리하기 위해 각각의 벡터에 0을 넣어준다. 오름차순으로 정렬한 뒤 lower_bound와 upper_bound를 사용해서 결괏값을 구해준다. ( 각 함수는 해당 값이 배열에서 처음 등장하는 주소와 해당 값을 초과하는 값이 배열에서 처음 등장하는 주소를 반환하고 이를 이용해서 해당 값이 몇 개 나오는지 알 수 있다) 각 함수의 사용법은 아래 주소에서 확인할 수 있다.
https://zz12345.tistory.com/17
백준 10816번 : 숫자 카드 2 (C++) (upper_bound , lower_bound)
https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카..
zz12345.tistory.com