ALGORITHM/BOJ
[백준] 1806 부분합
0298
2021. 1. 6. 13:44
1806번: 부분합
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
www.acmicpc.net
2021-01-06
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main1806 {
public static int N, S, arr[], answer;
public static void main(String[] args) throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken());
S = Integer.parseInt(st.nextToken());
arr = new int[N];
st = new StringTokenizer(bf.readLine());
for(int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
answer = 987654321;
int start = 0;
int end = 0;
int sum = 0;
while(start < N) {
if(sum >= S) {
if(answer >= (end-start)) {
answer = end-start;
}
sum -= arr[start++];
}else if(end == N) break;
else sum += arr[end++];
}
if(answer == 987654321) answer = 0;
System.out.println(answer);
}
}
|
cs |
#문제풀이
[백준] 2003 수들의 합2
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,0..
void2017.tistory.com
앞서 풀었던 투 포인터 알고리즘을 이용한 문제에서 살짝 응용된 문제이다.
같은 방법으로 이번엔 경우의 수를 구하는 것이 아니라 길이를 구하면 된다.
+) 여기서 25%에서 계속 틀려서 도대체 원인이 뭘까 생각했는데 첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.
이 부분을 놓쳐서 생겼던 문제이다. 32번째 줄을 추가했더니 통과했다...