zz12345의 코딩 공부

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==&& tt==1)
                {
                    apizza.pop_back();
                }
                if(i==&& 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==&& tt==1)
                {
                    bpizza.pop_back();
                }
                if(i==&& 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

 

공유하기

facebook twitter kakaoTalk kakaostory naver band