[백준 2003][🤍3] 수들의 합 2 (투포인터 알고리즘)

🚀 난이도

🤍 실버 3

🚀 문제

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

예제 입력 1 
4 2
1 1 1 1
예제 출력 1 
3

예제 입력 2 
10 5
1 2 3 4 2 5 3 1 1 2
예제 출력 2 
3

🚀 내 풀이 ⭕

#include <iostream>
#include <vector>
using namespace std;

int answer = 0;
int main() {
    int N, M;

    cin >> N >> M;
    vector<int> arr(N);
    for (int i = 0; i < N; ++i)
        cin >> arr[i];

    int start = 0;
    int end = 0;
    int sum = arr[0];
    while (end < N) {       
        if (sum < M) {
            end++;
            if (end < N)
                sum += arr[end];
        }
        else if (sum > M) {
            sum -= arr[start];
            start++;
        }
        else if (sum == M) {
            sum -= arr[start];
            start++;   
            end++;
            if (end < N)
                sum += arr[end];
            answer++;
        }
    }

    cout << answer;
}

• 구간의 모든 원소의 합이 M 이 되는 구간을 구해야 한다.
• 두 포인터가 같은 방향으로 움직이므로 첫 번째 원소 인덱스부터 시작

• 현재 구간의 합이 M보다 작으면
  • 아직 M보다 작으니까 M에 근접하도록 합을 증가시키기위해 구간에 다른 수를 더 포함해야 한다.
    • ex) 1 [2 3 4] 5 6 👉 1 [2 3 4 5] 6
    • start는 냅둔다.
    • end 를 증가시킨 후 sum 에 arr[end] 를 더한다.
• 현재 구간의 합이 M보다 크면
  • M보다 커져버렸으면 M에 근접하도록 감소시키기 위해 현재의 구간에서 원소를 빼야 한다.
    • ex) 1 [2 3 4] 5 6 👉 1 2 [3 4] 5 6
    • sum 에 arr[start] 를 빼주고 start를 증가시킨다.
    • end는 냅둔다.
• 현재 구간의 합이 M과 일치한다면
  • 조건에 일치하는 구간이므로 카운팅한다!
  • 현재 구간은 답이 되기 때문에 이 구간에서 앞으로 arr[start] 를 빼거나 arr[++end] 를 포함시켜도 답은 될 수 없을게 빤해서 그냥 둘 다 동시에 arr[start] 를 빼고 arr[++end] 를 더해주도록 한다.
    • ex) 1 [2 3 4] 5 6 👉 1 2 [3 4 5] 6

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

• 답은 3 개
  • 1 [2 3] 4 2 5 3 1 1 2
  • 1 2 3 4 2 [5] 3 1 1 2
  • 1 2 3 4 2 5 [3 1 1] 2

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기