[BOJ - JAVA] 2003 - 수들의 합 2 (두 포인터)

# 주소

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

2003번: 수들의 합 2

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
class Main{
    static int n, m;
    static int[] arr;
    static int answer = 0;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        arr = new int[n];
        for(int i = 0; i < n; i++)
            arr[i] = scan.nextInt();
        int start = 0;
        int end = 0;
        while(end < n){
            int sum = 0;
            for(int i = start; i <= end; i++){
                sum += arr[i];
            }
            if(sum == m){
                start++;
                end++;
                answer++;
            }
            else if(sum < m){
                end++;
            }
            else {
                start++;
                end = start;
            }
        }
        System.out.println(answer);
    }
}

두 포인터 문제중 비교적 쉬운 문제였습니다.

제 블로그에서 첫 두 포인터 문제입니다.

두 포인터 문제는 start인덱스와 end 인덱스를 가지고 이를 조절해가며 문제를 해결해나가야 합니다.

이를 위해 HashSet과 HashMap, Queue 등의 자료구조가 쓰일 수 있습니다.

이 문제의 경우 int 타입의 1차원 배열만 가지고도 풀 수 있습니다.

Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
arr = new int[n];
for(int i = 0; i < n; i++)
    arr[i] = scan.nextInt();

arr를 입력 받습니다.

int start = 0;
int end = 0;

이후 start와 end를 0으로 초기화 합니다.

while(end < n){
    int sum = 0;
    for(int i = start; i <= end; i++){
        sum += arr[i];
    }
    if(sum == m){
        start++;
        end++;
        answer++;
    }
    else if(sum < m){
        end++;
    }
    else {
        start++;
        end = start;
    }
}

start인덱스부터 end인덱스까지 다 더했을 때 m이 되면 다음의 인덱스로 넘어가기 위해 start와 end를 1씩 증가시키고 answer도 증가시킵니다.

또한 sum이 m보다 작을 땐 end만 증가시켜서 그 다음, 그 다음 인덱스까지 탐색합니다.

sm이 m보다 클 때에는 sum의 값을 더 좁혀야 하므로 start를 증가시키고 end의 값을 start로 둡니다.

이후 다시 sum값을 점점 증가시켜 나가며 경우의 수를 찾도록 합니다.

이 문제를 해결하려면 왼쪽과 오른쪽에서 범위를 좁혀가며 문제를 이해하는 능력이 필요한 것 같습니다.

감사합니다.