[코딩테스트] 백준 - 수들의 합 2

백준 - 수들의 합 2003번 [2일차]

시간제한	메모리 제한
0.5초	128MB

문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

 

출력

첫째 줄에 경우의 수를 출력한다.

 

나의코드

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 {
        // 수들의 합2 - 2003번
        // 배열을 순서대로 탐색해야함

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int num1 = Integer.parseInt(st.nextToken());
        int num2 = Integer.parseInt(st.nextToken());

        int [] array = new int[num1];
        String[] line = br.readLine().split(" ");

        int sum = 0, start = 0, end = 0, count = 0;


        //배열 저장
        for(int i =0 ; i < num1; i++){
            array[i] = Integer.parseInt(line[i]);
        }

        //탐색
        while (true){
            if(sum >= num2){ //합이 num 보다 크거나 같다면
                sum -= array[start++]; // 값을 빼주고 start++
            }else if(end == num1){ //end가 맨 끝에 도착했을 경우
                break; //반복문 끝냄
            }else { //합이 num 보다 작다면
                sum += array[end++];
            }

            if(sum == num2){ //start가 num 과 일치 한다면
                count++; // count증가
            }
        }

        System.out.println(count);

    }
}

 

해당 문제에서 배열저장 까지는 했는데 다음에 탐색하는 부분에서 한참을 고민했다

여러 for문과 if문을 써보다가 결국에 알아낸 방법은 투포인터를 활용해 풀어야 하는 문제였다!

 

이번 문제를 통해 투포인터 알고리즘에 대해 공부할 수 있었다
https://jjuya.tistory.com/109