Easy is Perfect

[백준] 2003번 C/C++ 풀이 _ 수들의 합 2

  • melonicedlatte
  • Aug 31, 2018


출처 : https://www.acmicpc.net/problem/2003 

수들의 합 2 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
0.5 초128 MB66533137232251.646%

문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i]+A[i+1]+…+A[j-1]+A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다.

예제 입력 1 

4 2
1 1 1 1

예제 출력 1 

3

예제 입력 2 

10 5
1 2 3 4 2 5 3 1 1 2

예제 출력 2 

3

출처

  • 데이터를 추가한 사람: isku

알고리즘 분류

풀이 


이 문제는 위와 같은 과정을 거쳐서 O(N) 으로 풀 수 있습니다. 
구간의 연속된 합이기 때문에 left, right 포인터를 한 칸씩 전진시키면서 조건에 따라서 구분하면 됩니다. 

left와 right 는 무조건 한 번에 하나는 이동하기 때문에, N+N 으로 시간 복잡도는 O(N)입니다. 
이러한 개념을 '투포인터' 라고 합니다. 

소스코드

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
#include <iostream> 
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
int main(void) {
    ios::sync_with_stdio(false);
    LL N, M, answer = 0;
    cin >> N >> M;
    LL * A = (LL*)malloc(sizeof(LL)*(N + 1));
    for (LL n_idx = 1; n_idx <= N; n_idx++)
        cin >> A[n_idx];
 
    // left와 right 를 이동시키면서 합과 같은 녀석이 나오면 답++
    LL left = 1, right = 1, sum = 0;
    while (left <= right && right <= N + 1) {
        if (sum >= M) {
            if (sum == M) answer++;
            sum -= A[left++];
        }
        else {
            if (right == N + 1) break;
            sum += A[right++];
        }
    }
    cout << answer;
    return 0;
}
cs



Search