[BOJ] 백준 2003 수들의 합 2

Approach

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

 

특정 구간에 있는 원소들 합 == M 인 구간이 몇개인지 구하는 문제이다.

N개의 원소에 나올 수 있는 모든 구간을

이중 for문으로 전수 조사해서 구할 수 있다.

void process() 
{
	for (int s = 0; s < N; ++s)
	{
		for (int e = s; e < N; ++e)
		{
			sum = 0;
			for (int i = s; i <= e; ++i)
			{
				sum += arr[i];
			}

			if (sum == M)
			{
				ans++;
			}
		}
	}
}

하지만 N^2 의 시간복잡도가 나오는데, "시간 초과" 결과가 나온다.

---

해당 문제는 투 포인터 기법을 이용해서 풀 수 있다.

처음 원소 시작점에서 [s, e]를 구간을 잡아서

해당 구간의 합 sum < M 이면 e를 증가시켜 구간 범위를 넓혀주고

구간의 합 sum >= M 이면 s를 증가시켜 구간 범위를 좁혀준다.

각 원소는 양수이므로, 구간 범위 합(sum)이 e가 증가할 때는 증가하지만

s가 증가할 때는 감소한다고 볼 수 있다.

 

변수 e가 끝지점인 N에 도달한다면 더 이상 구간을 늘릴 수 없기 때문에

탐색 종료 시점으로 둘 수 있다.

 

C++

#include <stdio.h>

const int MAX_N = 1e4 + 5;
int N, M, ans, sum, s, e;
int arr[MAX_N];

void process()
{
	while (true)
	{
		if (sum < M)
		{
			if (e == N) break;
			sum += arr[e++];
		}
		else  // sum >= M
		{
			sum -= arr[s++];
		}

		if (sum == M) ans++;
	}
}

int main() 
{
	// freopen("input.txt", "r", stdin);
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &arr[i]);
	}
		
	process();

	printf("%d\n", ans);
}

 

Java

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
	
		int N = Integer.parseInt(sc.next());
		int M = Integer.parseInt(sc.next());
		
		int[] arr = new int[N];
		
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(sc.next());
		}
		
		int count = 0;
		int idx = 0;
		while(true) {
			int sum = 0;
			for(int i=idx; i<N; i++) {
				sum += arr[i];
				if(sum == M) {
					count++;
					break;
				}else if(sum > M) {
					break;
				}
			}
			idx++;
			if(idx >= N) {
				System.out.println(count);
				break;
			}
		}
	}
}