https://www.acmicpc.net/problem/2003
2003번: 수들의 합 2
첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.
www.acmicpc.net
dp로 list의 연속 합을 구현하였고 two pointer로 인덱스를 조정해가며 M과 비교하였습니다.
l~r의 합이 M과 같으면 정답인 경우이므로 ans++
l~r의 합이 M보다 작으면 수를 더해야하므로 r++
l~r의 합이 M보다 크면 수를 빼야하므로 l++
이 과정을 반복하여 r이 list.length와 같아지면 중지하면 됩니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static int list[], dp[]; static int N, M, ans; static void func() { int l = 1; int r = 1; while (r < list.length) { if (dp[r] - dp[l - 1] == M) { ans++; l++; } else if (dp[r] - dp[l - 1] > M) { l++; } else r++; } System.out.println(ans); } static void input() throws Exception { st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); list = new int[N + 1]; dp = new int[N + 1]; st = new StringTokenizer(br.readLine()); for (int i = 1; i <= N; i++) { list[i] = Integer.parseInt(st.nextToken()); dp[i] = dp[i - 1] + list[i]; } } public static void main(String[] args) throws Exception { input(); func(); } } | cs |
'algorithm > Two-Pointer' 카테고리의 다른 글
| boj 1253 좋다 (0) | 2021.10.21 |
|---|---|
| boj 9024 두 수의 합 (0) | 2021.10.21 |
| boj 17609 회문 (0) | 2021.03.29 |
| boj 2559 수열 (0) | 2021.02.12 |
| boj 1806 부분합 (0) | 2021.01.22 |