https://www.acmicpc.net/problem/2143

 

2143번: 두 배열의 합

첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다

www.acmicpc.net

[풀이]

 

2632번 피자판매와 비슷한 문제인데 숫자 범위가 커져서 구간합의 개수를 배열에 저장할 수가 없다.

그래서 맵을 사용해서 저장하였다. 그 외에는 2632번과 동일하다.

 

주의할 점은 결과값을 int형에 저장하면 72%에서 오답이 나온다.

T(-1,000,000,000 ≤ T ≤ 1,000,000,000)이고 각 원소의 절댓값이 1000000 이하이기 때문에 합을 구하는

과정은 int형 안에 다 들어오게 된다.

T와 구간합의 범위에만 신경쓰다보니 경우의 수가 int 범위를 넘어갈 수 있다는 것을 놓쳤다.

1<=n<=1000, 1<=n<=1000이므로 최대 1000*1000*1000*1000의 경우의 수가 나올 수 있다.

(가장 간단하게 n,m이 1000, 모든 원소가 0, T가 0인 경우..)

 

경우의수 나오는 문제는 특히 자료형에 주의

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
#include <cstdio>
#include <map>
 
using namespace std;
int t, n, m, A[1000], B[1000];
long long ret;
int main() {
 
    scanf("%d%d", &t,&n);
    for (int i = 0; i < n; i++) scanf("%d", &A[i]);
    scanf("%d", &m);
    for (int i = 0; i < m; i++) scanf("%d", &B[i]);
    map<long long, long long> aMap;
 
    for (int i = 0; i < n; i++) {
        long long sum = 0;
        for (int j = i; j < n; j++) {
            sum += A[j];
            aMap[sum]++;
        }
    }
 
    for (int i = 0; i < m; i++) {
        long long sum = 0;
        for (int j = i; j < m; j++) {
            sum += B[j];
            ret += aMap[t - sum];
        }
    }
 
    printf("%lld", ret);
}
cs
https://github.com/has2/Algorithm/blob/master/boj/%EC%95%84%EB%AC%B4%EA%B1%B0%EB%82%98/2143.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/백준] 2632 : 피자판매 (C++)  (0) 2020.06.30

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

+ Recent posts

티스토리툴바