[코테] 백준 2003번 : 수들의 합 2 (java)

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

 

알고리즘 분류 : 브루트포스 알고리즘, 누적합, 투포인터

❓문제

---

🔅해석

두 수의 합이 특정 값이 되는 경우를 찾는 문제로 투포인터를 이용한다.

입력받은 숫자를 배열에 넣고 low pointer와 high pointer로 합을 구한다. 

 

//입력
10 5
1 2 3 4 2 5 3 1 1 2

 

1) 초기화 및 sum < M

두개의 포인터 모두 0번째 인덱스부터 출발하고 sum은 0번째 인덱스 값으로 초기화해준다.

sum이 특정 값(M) 5보다 작으므로 high pointer를 +1 해준다. 그리고 sum에 증가된 high 번째의 값을 더한다.

 

 

 

2) sum == M

sum == M 이 될 때, cnt++ 해주고 low 또는 high을 +1 해준다. 그리고 sum에 증가된 high 번째의 값을 더한다.

 

 

3) sum > M

sum이 M 보다 커졌을 때는 sum에서 현재 low번째 값을 빼주고 low pointer를 +1 해준다.

 

---

⭕정답 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int N, M;
	static int[] numbers;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		numbers = new int[N + 1];
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			numbers[i] = Integer.parseInt(st.nextToken());
		}

		int cnt = 0;
		int low = 0, high = 0;
		int sum = numbers[low];
		while (true) {
			if (high >= N)
				break;

			if (sum > M) {
				sum -= numbers[low++];
			} else if (sum == M) {
				cnt++;
				sum += numbers[++high];
			} else {
				sum += numbers[++high];
			}
		}
		System.out.println(cnt);
		br.close();

	}
}

 

---

❗결과