백준 2003번 [수들의 합 2](C++) -yes6686- 티스토리

백준 문제 풀이: 2003 [수들의 합 2]

---

문제 링크: https://www.acmicpc.net/problem/2003

문제 설명:

길이가 \(N\)인 수열에서 연속된 부분 수열의 합이 \(M\)이 되는 경우의 수를 구하는 문제입니다. 부분 수열은 비어 있지 않으며, 같은 위치의 수를 여러 번 사용할 수 없습니다.

---

문제 해결 코드

// 수들의 합 2 문제 해결 코드
#include <iostream>
using namespace std;

int arr[10001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    // 수열 입력
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int start = 0, end = 0, sum = 0, ans = 0;

    // 투 포인터를 사용한 연속 부분 수열 합 계산
    while (end <= n) {
        if (sum < m) {
            sum += arr[end++];
        } else if (sum > m) {
            sum -= arr[start++];
        } else {
            ans++;
            sum += arr[end++];
        }
    }

    cout << ans << '\n';
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘:
  • 투 포인터 기법을 사용하여 연속된 부분 수열의 합을 계산합니다.
  • 두 개의 포인터 start와 end를 이용해 현재 부분 수열의 합을 유지하며, 목표 합 M에 도달하는 경우를 카운트합니다.
• 구현 세부사항:
  • sum: 현재 부분 수열의 합을 저장하는 변수입니다.
  • start와 end: 부분 수열의 시작과 끝을 가리키는 포인터입니다.
  • 현재 합 sum이 M보다 작으면 end를 증가시켜 범위를 확장합니다.
  • sum이 M보다 크면 start를 증가시켜 범위를 축소합니다.
  • sum == M인 경우 정답을 증가시키고 end를 이동합니다.
• 시간 복잡도 분석:
  • 각 포인터 start와 end는 한 방향으로만 이동하며, 배열을 최대 한 번씩 순회합니다.
  • 시간 복잡도: \(O(n)\)

---

결과

이 알고리즘은 입력된 수열에서 연속된 부분 수열의 합이 주어진 값 \(M\)이 되는 경우의 수를 효율적으로 계산합니다. 예를 들어:

• 입력:

          4 2
          1 1 1 1
          

• 출력: 3

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!