[백준] 2003: 수들의 합

0. 문제 주소

 

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

2003번: 수들의 합 2

 

 

1. 풀이

 

투 포인터 문제.

 

 

왼쪽과 오른쪽 포인터들을 각각 어느 조건에서 움직여야 하는지, 종결 조건은 무엇인지

순서가 항상 헷갈렸다. 생각해볼 점은 다음과 같다.

 

 

0. 왼쪽 포인터를 L, 오른쪽 포인터를 R이라 하자.

1. 주어진 배열의 수들은 모두 자연수이다.

2. 1.의 이유로 R을 오른쪽으로 옮기면, L과 R이 나타내는 구간합은 무조건 커진다.

3. 반대로 L을 오른쪽으로 옮기면, 구간합은 무조건 작아진다.

 

 

R을 오른쪽으로 옮기는 조건을 중점으로 while문을 정리해보면,

1. 구간합이 주어진 값보다 크거나 같다면 : 더 작은 구간합의 경우를 볼 필요가 있으므로 L을 옮긴다.

2. 1.이 아닌데도, 즉 구간합이 주어진 값보다 작은데도 이미 R이 배열의 끝에 도달했으면 : 루프 탈출

 - R이 끝에 도달했을 때, 할 수 있는 행동은 L을 옮기는 것 뿐이다. 하지만 구간합이 주어진 값보다 작으므로

   L을 더 옮겨봤자 구간합은 작아질 뿐이므로 루프를 탈출

3. 1, 2가 전부 아닐 때, 즉 구간합이 주어진 값보다 작으면서 R이 아직 끝에 도달하지 않았다면 : R을 옮긴다.

 

 

다음과 같은 조건으로 L과 R을 이동시키며 while문의 맨 마지막에 구간합이 M이 되는지 검사해주면 된다.

 

L과 R은 0으로 초기화해주고, L ~ (R-1)번째 원소의 합까지라고 생각해야 쉽다.

 

 

2. 풀이 코드

 

* 유의할 점

 

#include <iostream>

#define MAX 10005

using namespace std;

int N, M;
int ans;
int nums[MAX];

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    scanf("%d %d", &N, &M);
    for (int i=0;i<N;i++){
        scanf("%d", &nums[i]);
    }
    
    int a = 0, b = 0, sum = 0;
    while(1){
        if (sum >= M){
            sum -= nums[a++];
        }
        else if (b == N) break;
        else{
            sum += nums[b++];
        }
        if (sum == M) ans++;
    }
    
    printf("%d\n", ans);

    return 0;

}