https://www.acmicpc.net/problem/2632
2632번: 피자판매
첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 ( 3≤m, n�
www.acmicpc.net
[풀이] 완전탐색,부분합
1. n,m 제한이 1000이므로 모든 연속된 구간의 합 sum을 계산한다.
2. sum이 어떤 구간에 있는지는 중요하지 않고 몇개나 나올 수 있는지가 중요하므로
Acnt,Bcnt 배열을 각각 만들에 sum이라는 값이 몇번 나올 수 있는지를 저장한다.
3. 1,2 과정은 피자 A와 B에 대해 중복되는 연산이므로 func 함수를 만들어서 중복코드를 줄인다.
4. func에서 sum을 구할 때 i를 구간의 크기로 잡는 피자 조각이 n개라면 1에서 n까지 돌아야 한다.
j는 시작 index로 정한다. 최초 index 0부터 시작하는 i 구간만큼의 sum을 구한다.
그 뒤의 for문은 j를 옮겨가면서 앞에는 빼주고 뒤에는 더해주는 과정이다.
i가 최대 크기인 경우엔 이 과정은 break.
5. A,B 한개의 피자에서만 조각을 모두 가져올 수도 있으므로 func에서 sum을 구하는 도중에 답을 더해준다.
6. Acnt,Bcnt를 모두 구했으면 곱연산으로 경우의 수를 구한다.
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 | #include <cstdio> int k,n,m,A[1000], B[1000],Acnt[2000001], Bcnt[2000001],ret; void func(int p, int arr[], int arrCnt[]) { for (int i = 1; i <= p; i++) { int sum = 0; for (int j = 0; j < i; j++) sum += arr[j]; arrCnt[sum]++; if (sum == k) ret++; if (i == p) break; for (int j = 1; j < p; j++) { sum -= arr[j - 1]; sum += arr[(j + i - 1) % p]; arrCnt[sum]++; if (sum == k) ret++; } } } int main() { scanf("%d%d%d", &k, &n, &m); for (int i = 0; i < n; i++) scanf("%d", &A[i]); for (int i = 0; i < m; i++) scanf("%d", &B[i]); func(n, A, Acnt); func(m, B, Bcnt); for (int i = 1; i < k; i++) { int j = k - i; ret += Acnt[i] * Bcnt[j]; } printf("%d", ret); } | cs |
https://github.com/has2/Algorithm/blob/master/boj/%EC%95%84%EB%AC%B4%EA%B1%B0%EB%82%98/2632.cpp
'Problem-Solving > BOJ' 카테고리의 다른 글
| [BOJ/백준][Gold4] 10830 : 행렬 제곱(C++) (0) | 2020.12.12 |
|---|---|
| [BOJ/백준][Gold4] 1403 : 거짓말(C++) (0) | 2020.12.12 |
| [BOJ/백준][Gold4] 1022 : 소용돌이 예쁘게 출력하기 (C++) (0) | 2020.12.12 |
| [BOJ/백준] 2624: 동전 바꿔주기 (C++) (0) | 2020.07.28 |
| [BOJ/백준] 2143: 두 배열의 합(C++) (0) | 2020.07.05 |