https://www.acmicpc.net/problem/1806
1806번: 부분합
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
www.acmicpc.net
연속된 수들의 부분합이기 때문에 two pointer로 해결할 수 있습니다.
저는 two pointer와 dp를 사용하였습니다.
우선 dp에 연속합을 저장해놓고
l~r의 합이 S보다 작으면 r++
l~r의 합이 S보다 크거나 같으면 ans을 갱신하고 l++
이 과정을 반복하여 ans을 출력하였습니다.
예외처리로 모든 값을 더해도 S보다 작다면 0을 출력합니다.
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, S, ans = 100000; static void func() { int l = 1; int r = 1; while (r <= N) { if (dp[r] - dp[l - 1] < S) { r++; } else { ans = Math.min(ans, r - l + 1); l++; } } if (ans == 100000) ans = 0; System.out.println(ans); } static void input() throws Exception { st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); S = 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 2003 수들의 합 2 (0) | 2021.01.22 |