[백준/BOJ] 2003번: 수들의 합 2

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

해설

for문을 통해 모든 경우의 수를 탐색하고자 하면 시간 초과가 난다.

이 문제에선 투 포인터 알고리즘을 사용해야 한다.

투 포인터 알고리즘은 1차원 배열이 있을 때 2개의 포인터(인덱스)를 조작해가며 원하는 값을 얻는 형태이다.

 

2개의 포인터를 low, high이라 하고 초기값은 0으로 두었다.

이제 sum(합을 저장하는 변수)의 값에 arr[high++]을 해준다.

이를 반복하면 우리가 원하는 값인 M보다 sum이 크거나 같게 될 것이다.

이때 sum의 값에서 arr[low++]을 하여 배열의 초기값을 증가시킨다.

 

밑의 예시를 보면 이해에 좀 더 도움이 될 것이다.

 

만약 sum의 값이 M과 같다면 cnt를 증가시켜주며, sum에 low포인터가 가리키는 값을 빼고 한칸 증가시킨다.

만약 2 3 2와 같은 경우가 있을 때 2 + 3 = 5이지만, 3 + 2도 5가 되기 때문에 M과 sum이 같을 때도 low가 가리키는  값을 뺸다.

 

이를 반복하다 high 포인터가 N에 도달할 경우 반복문을 탈출해준다.

소스 코드

import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    var st = StringTokenizer(readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()
    val arr = IntArray(n)
    st = StringTokenizer(readLine())
    for(i in 0 until n) arr[i] = st.nextToken().toInt()

    var sum = 0
    var low = 0
    var high = 0
    var cnt = 0
    while(true) {
        if(sum >= m) sum -= arr[low++]
        else if(high == n) break
        else sum += arr[high++]

        if(sum == m) cnt++
    }
    println(cnt)
}