백준 2003 수들의 합 2 c++, Kotlin (투 포인터)

문제 출처 : 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이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

알고리즘 분류

• 두 포인터

풀이

투 포인터 기본 문제이다.

주어진 리스트는 모두 자연수이고,

리스트의 연속된 수의 합이 m이어야 하므로, 

start 포인터와 end 포인터를 두고,

start~end 구간의 합이 m보다 작다면 end포인트를 우측으로 이동시킨다. (합이 커진다)

start~end 구간의 합이 m보다 크다면 start포인트를 우측으로 이동시킨다. (합이 작아진다)

start~end 구간의 합이 m과 같다면 답을 1 증가시키고, start포인트를 우측으로 이동시킨다. (합이 작아진다)

위의 과정을 start 혹은 end 포인터가 배열을 벗어나면 종료한다.

 

코드(c++)

#include <iostream>

using namespace std;

int arr[10000];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	int answer = 0;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int p1 = 0, p2 = 0;
	int sum = 0;
	while (p1 < n) {
		if (sum == m) {
			answer++;
		}
		else if (sum > m) {
			sum-=arr[p1++];
			continue;
		}

		if (p2 < n) {
			sum += arr[p2++];
		}
		else {
			sum -= arr[p1++];
		}

	}
	cout << answer;
}

코드(Kotlin)

import java.util.StringTokenizer

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    var tk = StringTokenizer(br.readLine())
    val (n,m) = List(2){ Integer.parseInt(tk.nextToken())};
    tk = StringTokenizer(br.readLine())
    val arr = IntArray(n)
    for(i in 0 until n){
        arr[i]= Integer.parseInt(tk.nextToken())
    }
    var s=0
    var e=0
    var sum =0
    var answer=0

    while(s<n){
        if(sum>m){
            sum -=arr[s++]
        }
        else if(sum==m){
            sum-=arr[s++]
            answer++
        }
        else{
            if(e <n){
                sum += arr[e++]
            }
            else {
                sum -= arr[s++]
            }
        }
    }
    write("$answer")
    close()
}