[BOJ] 백준 2003. 수들의 합 2

문제

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

2003번: 수들의 합 2

---

풀이

 문제의 조건에서 N의 input size가 최대 10,000 입니다. 만약 배열을 두 번 돌게 된다면 시간 복잡도 O(N^2)는 1억으로 1초가 넘어가 문제의 시간 제한 조건인 0.5초를 넘어가게 됩니다.

 

 그래서 이 문제는 투 포인터를 통해 접근해야 합니다.

 

 

매커니즘의 순서는 다음과 같습니다.

 

1. 만약 sum이 M과 같다면, cnt를 증가시키고, right의 값을 증가시킵니다.

2. sum이 M보다 작다면, right를 증가시켜 부분 수열의 범위를 늘립니다.

3. sum이 M보다 크다면, left를 증가시켜 부분 수열의 범위를 줄입니다.

 

1. 초기 상태

nums: [1, 1, 1, 1] 

sum: 0 cnt: 0

 

2. right를 이동하면서 sum에 숫자를 더함.

nums: [1, 1, 1, 1]
  left ^ right
   
sum: 1 cnt: 0

 

3. 더해간 결과, sum이 M과 같아지면 cnt를 증가시키고 right를 한 칸 이동

nums: [1, 1, 1, 1]
  left ^  ^ right
               
sum: 2 cnt: 1

 

4. 이제 sum이 M보다 크므로 left를 증가. 이를 위해 left를 한 칸 이동하고 sum에서 해당 값을 빼준다.

nums: [1, 1, 1, 1]
     left ^ right
          
sum: 1 cnt: 1

 

left가 N보다 작거나 같고 right가 N보다 작거나 같은 동안 위 과정을 반복합니다.

 

 

 

매우 유사한 문제로 백준 1806. 부분 합 문제가 있습니다. 조금의 응용만 하면 되니 함께 풀어보시는 걸 추천합니다. (관련 포스팅)

---

소스 코드

import java.util.Scanner;

public class B2003_수들의합2 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] nums = new int[N+1];
        for(int i = 0; i<N;i++){
            nums[i] = sc.nextInt();
        }
        int left = 0;
        int right = 0;
        int sum = 0;
        int cnt = 0;

        while(left<=N&&right<=N){
            if(sum==M) {
                cnt++;
                sum += nums[right++];
            }
            if(sum<M) sum += nums[right++];
            if(sum>M) sum -= nums[left++];
        }
        System.out.println(cnt);
    }
}