[백준 Java] 수들의 합2

🔗 문제링크 🔗

2003번: 수들의 합 2

---

🌟 생각 흐름 🌟

이런 비슷한 문제를 기업코테에서 한번 본적이 있다.

부분합을 이용한 문제여서 해당 아이디어만 알고 있다면 쉽게 해결 할 수 있다.

index	1	2	3	4	5
갑	1	2	3 1️⃣ (현재값)	2	1
연속된 수의 합	1	3 2️⃣ (이전 값까지의 합)	6 1️⃣ + 2️⃣ =  3️⃣	8	9
부분적인 합을 구하는방법	arr[1] - arr[0] =1	arr[2]-arr[1]=2	arr[3]-arr[2]=3	arr[4]-arr[3]=2	arr[5]-arr[4]=1

즉 이런식으로 1~5번 까지의 합에서 1~2번까지의 합을 빼면 3~5번 까지의 합을 알 수 있다.

arr[5] - arr[2] = 9 - 3 = 6 ( arr[3] + arr[4] + arr[5] ) 

 

문제를 보면 연속된 숫자의 합들중에 m이 나올 수 있는 경우의 수를 구하라고 하였다. 

근데 연속된 경우이고 조건 상 모두 양수이기 때문에 만약 지금 부분의 합이 m보다 크면 앞의 숫자를 버리고 지나와야 한다는 소리이다.

만약 m이 4라면 (1 + 2 + 3) < 4이기 때문에 앞의 부분은 버려야 한다는 소리이다. 

 

이 방법을 이용해서 현재 부분인데스의 범위를 startIdx 와 i를 두고 arr[i]-arr[startIdx]를 이용하면 (startIdx+1 ~ i 부분)까지의 합을 이용할 수 있다. 그리고 만약 현재 (startIdx+1 ~ i 부분)이 m을 넘어 갔다면 startIdx를 한칸 오른쪽으로 옮기면 된다. 해당 방식으로 문제를 풀어나가면 해결할 수 있다.

 

---

🍳 코드 🍳

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); //숫자의 개수
        int m = Integer.parseInt(st.nextToken()); //목표 합
        long[] subSum = new long[n + 1]; //부분합 저장
        int startIdx = 0; //시작 위치

        st = new StringTokenizer(br.readLine());
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            int now = Integer.parseInt(st.nextToken());
            subSum[i] = subSum[i - 1] + now;

            while (m < subSum[i] - subSum[startIdx]) {
                startIdx++;
            }

            if (m == subSum[i] - subSum[startIdx]) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}