[백준 2003] 수들의 합 2

0. 제목

• 백준 2003 수들의 합 2
• BOJ 2003 수들의 합 2
• C++ 2003 수들의 합 2

---

1. 문제

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

---

2. 풀이

• startIdx를 이용해 합의 시작점을 저장해준다.
• sum이 구하고자 하는 합 M과 같아지면 가능한 경우의 수인 cnt를 1증가시켜주고 M을 넘어가면 while문을 빠져나간다.
• 만약 while문에서 sum이 M보다 작고 startIdx가 배열의 마지막 원소를 지나치면 즉, N+1 이 되면 while문을 빠져나온다.
• cnt를 출력하면 정답니다.
• 그런데 이러한 문제는 투포인터를 사용한다고 하면 된다. 위 방법도 그와 비슷한 방법이지만 투포인터의 내용을 살려 또 다른 코드를 첨부하겠다.
• 투포인터 방식을 사용하면 위 방식보다 시간을 줄일 수 있다. 
• 투포인터 방식은 low, high 두 포인터를 설정해 놓은 후 sum의 크기에 따라 low와 high가 가리키는 위치를 조정하는 것이다. 
• high가 N이 되면 while문을 빠져나가고 그 내부에서는 sum이 M보다 커자면 low가 가리키는 값을 빼주고 high가 가리키는 값을 더해준다.
• low로 빼고 high로 채워준다고 생각하면 될 것 같다.

---

3. 코드

• 방법 1

#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int A[10001] = {0};
    int N, M;
    int cnt = 0;
    int startIdx = 1;
    int sum = 0;
    
    cin >> N >> M;
    for(int i = 1; i <= N; i++)
        cin >> A[i];
    
    for(int i = 1; i <= N; i++){
        startIdx = i;
        sum = 0;
        while(1){
            if(startIdx == N+1) break;
            sum += A[startIdx];
            if(sum == M){
                cnt++;
                break;
            }
            else if(sum > M)
                break;
            startIdx++;
        }
    }
    cout << cnt << '\n';
    return 0;
}
 

• 방법 2 (투포인터 방식)

#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int A[10001] = {0};
    int N, M;
    int l = 0, h = 0;//low, high
    int sum = 0, cnt = 0;
    
    cin >> N >> M;
    for(int i = 0; i < N; i++)
        cin >> A[i];
    
    while(1){
        if(sum >= M) sum -= A[l++];
        else if(h == N) break;
        else sum += A[h++];
        
        if(sum == M) cnt++;
    }
    
    cout << cnt << '\n';
    return 0;
}