[Baekjoon] 2003번: 수들의 합 2

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

2003번: 수들의 합 2

문제 설명

N개의 수로 된 수열이 주어진다. 이 수열의 i번째 수부터 j번째 수까지의 합이 M이 되는 경우의 수를 구하는 프로그램을 작성해야 한다. 예제 2로 설명하면 다음과 같다.

인덱스가 0인 1부터 시작해보자.

1. i = 0
   • 1부터 순서대로 더해나간다. 그러다 1 + 2 + 3 = 6이므로 이 경우는 안 된다.
2. i = 1
   • 2부터 순서대로 더해나간다. 그러다 2 + 3 = 5이므로 카운팅한다.
3. i = 2
   • 3부터 순서대로 더해나간다. 그러다 3 + 4 = 7이므로 이 경우는 안 된다.
4. i = 3
   • 4부터 순서대로 더해나간다. 그러다 4 + 2 = 6이므로 이 경우는 안 된다.
5. i = 4
   • 2부터 순서대로 더해나간다. 그러다 2 + 5 = 7이므로 이 경우는 안 된다.
6. i = 5
   • 5부터 순서대로 더해나간다. 그러다 5 = 5이므로 카운팅한다.
7. i = 6
   • 3부터 순서대로 더해나간다. 그러다 3 + 1 + 1 = 5이므로 카운팅한다.
8. i = 7
   • 1부터 순서대로 더해나간다. 1 + 1 + 2 = 4이므로 이 경우는 안 된다.
9. i = 8
   • 1부터 순서대로 더해나간다. 1 + 2 = 3이므로 이 경우는 안 된다.
10. i = 9
    • 1부터 순서대로 더해나간다. 2 = 2이므로 이 경우는 안 된다.

따라서 이 문제의 경우의 수는 3이 된다.

풀이 방법 1. 완전탐색

가장 간단한 방법으로 모든 경우의 수를 이중 반복문으로 해결할 수 있다. 다만 시간복잡도가 \(O(n^2)\) 이 된다는 단점이 있다. 로직은 단순하다. i부터 순서대로 모두 더하면서 sum이 M과 같으면 카운트한다.

private static int bruteForce() {
    int cnt = 0;
        
    for (int i = 0; i < N; i++) {
        int sum = 0;
        for (int j = i; j < N; j++) {
            if (sum < M) {
                sum += nums[j];
            } else if (sum >= M) {
                break;
            }
                
            if (sum == M) {
                cnt++;
            }
        }
    }
        
    return cnt;
}

풀이 방법 2. 투 포인터

투 포인터를 활용하면 시간 복잡도를 \(O(n)\) 까지 낮출 수 있다.

• start는 시작점, end는 끝점을 의미한다.
• end가 끝까지 도달하면 반복이 종료된다.
• 그리고 반복이 종료될 때까지 다음 과정을 반복한다.

1. sum이 M보다 작다면 sum에 nums[end]를 더하고 end를 뒤로 이동시킨다.
2. sum이 M보다 크거나 같으면 sum에서 nums[start]를 빼고 start를 뒤로 이동시킨다.
3. sum이 M과 같으면 카운팅한다.

과정을 간략하게 보면 다음과 같다.

시작

1회전

2회전

3회전

4회전

5회전

이런 식으로 계속 start와 end의 포인트를 변경해가면서 M과 같은 경우의 수를 찾아내는 것이다.

private static int twoPointer() {
    int cnt = 0;
    int start = 0, end = 0;
    int sum = 0;
        
    while (true) {
        if (sum >= M) {
            sum -= nums[start++];
        } else if (end >= nums.length) {
            break;
        } else {
            sum += nums[end++];
        }
            
        if (sum == M) cnt++;
    }
        
    return cnt;
}