코드 복사/붙여넣기 하는 당신이 아름답습니다.

2003 : 수들의 합 2

풀이

투포인터 조아!!
분할정복도 조아!!

코드

#include <stdio.h>
int n, m, k, s, a[10001];
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0, j = 0; i < n; i++) {
		scanf("%d", &a[i]);
		s += a[i];
		while (s > m) s -= a[j++];
		k += (s == m);
	}
	printf("%d", k);
	return 0;
}
#include <cstdio>
#include <algorithm>
using namespace std;

int n, k, a[10001], sum[10001];

int go(int l, int r) {
	if (l > r) {
		return 0;
	}

	int j = l, ret = 0, sum = 0, m = (l+r)/2;
	for (int i = l; i <= r; i++) {
		sum += a[i];
		while (sum > k && j < m) {
			sum -= a[j];
			j++;
		}
		if (i >= m && sum == k) {
			ret++;
		}
	}

	ret += go(l, m-1) + go(m+1, r);

	return ret;
}

int main() {
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		sum[i] = sum[i-1]+a[i];
	}

	printf("%d\n", go(1, n));

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-03-19 20:24

Read more posts by this author