[백준온라인] 2003번 수들의 합 2

문제 : https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

문제 요약 : 부분 수열의 합이 M이 되는 경우의 수 출력

입력	출력
1 ≤ n(A) ≤ 10000 1 ≤ M ≤ 300000000 1 ≤ A[x] ≤ 30000	부분 수열의 합이 M이 되는 경우의 수 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_2003.java

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
31168089	cbkpar	2003	맞았습니다!!	15164KB	164ms	Java 11	761B

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 {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n,m,i,s,l,r,t;
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		int[] arr = new int[n+1];
		st = new StringTokenizer(br.readLine());
		for(i=1;i<=n;i++) arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
		s = 0;
		l = 0;
		r = 1;
		while(true) {
			if(r>n) break;
			t = arr[r] - arr[l];
			if(t>=m) l++;
			if(t<=m) r++;
			if(t==m) s++;
		}
		System.out.println(s);
	}
}

해당 배열의 숫자가 모두 양수이므로 투포인터 방식으로 문제를 해결할 수 있다.

부분합을 미리 계산 후

l = 0, r = 1로 초기화 한 후

부분합이 원하는 값(m) 보다 크거나 같을 경우 l을 오른쪽으로 한 칸

부분합이 원하는 값(m) 보다 작거나 같을 경우 r을 오른쪽으로 한 칸

부분합이 원하는 값(m) 같을 경우 경우의 수를 1 증가시켜주며

r이 마지막 값을 본 경우에는 종료시켜준다.

 

 

 

- 단순하게 모든 경우의 수를 구한 코드

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
31148547	cbkpar	2003	맞았습니다!!	16796KB	272ms	Java 11	691B

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 {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n,m,i,j,s;
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		int[] arr = new int[n+1];
		st = new StringTokenizer(br.readLine());
		for(i=1;i<=n;i++) arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
		s = 0;
		for(i=0;i<n;i++) for(j=i+1;j<=n;j++) if(arr[j]-arr[i]==m) s++;
		System.out.println(s);
	}
}

위 방법은 배열의 값이 음수인 경우에도 적용될 수 있지만 시간복잡도가

투포인터[O(n)] 에서 모든 경우의수[O(n^2)]으로 증가하게 된다.