[백준] 수들의 합 2 (JAVA)

수들의 합2_2003

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

2003번: 수들의 합 2

문제 설명

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 문제이다.

---

문제 풀이

생각 과정

우선 떠오른 방법은 누적합을 이용하는 방법이다.

0번 인덱스부터 N-1인덱스까지 누적합을 구하고 i번째 누적합에서 0부터 i-1번째 인덱스까지의 값을 일일이 빼주는 

방식으로 구현을 했다.

 

그 다음으로 떠올린 방법은 투포인터이다.

시작점과 끝점을 정하고 합이 M보다 작으면 끝점을 뒤로 이동시켜 합에 더해주고

M보다 크면 시작점을 앞으로 하나 당겨서 합에서 빼주는 방식으로 구현을 했다.

구현 - 누적합

public class 수들의합2 {
    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());
        int[] A = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {	// 주어진 수 배열 A
            A[i] = Integer.parseInt(st.nextToken());
        }
        int[] sum = new int[N];	// 누적합 배열 sum
        sum[0] = A[0];
        for (int i = 1; i < N; i++) {
            sum[i] = A[i] + sum[i - 1];	// 누적합 계산
        }
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (sum[i] == M) {	//	 누적합이 M과 같으면 cnt증가
                cnt++;
            }else {
                int temp = sum[i];	
                for (int j = 0; j < i; j++) {
                    temp -= A[j];	// 누적합에서 하나씩 빼주며 계산
                    if (temp == M) {	// 빼준 값이 M과 같으면
                        cnt++;			// cnt 증가하고 종료
                        break;
                    }
                }
            }
        }
        System.out.println(cnt);
    }
}

구현 - 투포인터

public class 수들의합2_2003_투포인터 {
    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());
        int[] A = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        int cnt = 0;	// 경우의수
        int start = 0;	// 시작점
        int end = 0;	// 끝점
        int sum = 0;	// 합
        while (true) {
            if (sum >= M) {	// 합이 M보다 크거나 같으면 
                sum -= A[start++];	// sum에서 빼주고 시작점 앞으로
            } else if (end >= N){	// 전부 탐색한 경우 종료
                break;
            } else {	//	합이 M보다 작으면 
                sum += A[end++];	// sum에 더해주고 끝점 앞으로
            }
            if (sum==M) cnt++;	// sum이 M과 같으면 경우의수 증가
        }
        System.out.println(cnt);
    }
}

주의점

첫번째 방법은 시간복잡도가 O(N²)이고 투포인터의 경우 시간복잡도가 O(N)이다. 

이 문제보다 범위가 커질경우 첫번째 방법으로는 통과하지 못할 수도 있다.