[백준 2003] 수들의 합 2 (C++, Java)

문제 링크: www.acmicpc.net/problem/2003

2003번: 수들의 합 2

1. 주의할 점

- 두 포인터 or DP를 이용하여 해결한다

 

2. 구현

- 모든 수가 3만 이하의 자연수다 → i~j까지의 합이 Target번호라면, j이후의 Arr[] 배열의 원소를 더할 필요가 없다(더하면 초과하므로)

 

2-1) 두 포인터

- L,R를 모두 인덱스 번호 0부터 시작한다. Sum을 통해 L과 R 사이에 존재하는 모든 원소의 합을 저장한다

- Sum이 Target과 같은 경우, Cnt++를 수행한다

- Sum이 Target보다 크거나 같다면 L을 오른쪽으로 움직인다. 단, L이 R과 같다면 R을 움직이며, R이 인덱스의 끝이라면 종료한다

- Sum이 Target보다 작다면 R을 오른쪽으로 움직이며, R이 인덱스의 끝이라면 종료한다

- L 혹은 R을 움직일때마다 Sum의 값을 변화시킨다

 

2-2) DP

- i의 값을 0~Num-1까지 설정하며 i부터 j까지의 합을 DP 함수를 통해서 수행한다

- i~j까지의 합인 Sum이 Target과 같다면, Cnt++이후 Return한다

- Sum이 Target보다 크거나 j가 Num과 같다면 Return한다

- Sum이 Target보다 작다면 j의 값과 Sum의 값을 늘린다

 

[C++ : DP]

#include <iostream>
using namespace std;
long long arr[10000];
int num, tot;
long long result = 0;

void dp(int idx, long long sum) {
	if (idx == num)
		return;
	if (sum + arr[idx] == tot) {
		result++;
		return;
	}
	else if (sum + arr[idx] > tot)
		return;
	else if (sum + arr[idx] < tot)
		dp(idx + 1, sum + arr[idx]);
}

int main() {
	cin >> num >> tot;
	for (int i = 0; i < num; i++)
		cin >> arr[i];
	for (int i = 0; i < num; i++)
		dp(i, 0);
	cout << result;
	return 0;
}

 

[Java: 두 포인터]

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String ss = br.readLine();
	    StringTokenizer st = new StringTokenizer(ss);
	    int num = Integer.parseInt(st.nextToken());
	    int target = Integer.parseInt(st.nextToken());
		int arr[] = new int[num];
		ss = br.readLine();
		st = new StringTokenizer(ss);
		for(int i=0;i<num;i++)
		    arr[i] = Integer.parseInt(st.nextToken());
		
		int l=0,r=0,cnt=0;
		int sum=arr[0];
		while(l<=r && r<num){
		    if(sum>=target){
		        if(sum==target) cnt++;
		        if(l==r){
		            r++;
		            if(r==num) break;
		            sum+=arr[r];
		        }
		        else{
    		        sum-=arr[l];
    		        l++;
		        }
		    }
		    else{       //sum<target
		        r++;
		        if(r==num) break;
		        sum+=arr[r];
		    }
		}
		System.out.print(cnt);
	}
}