[BOJ]1806部和
9861 ワード
🔗 Problem
https://www.acmicpc.net/problem/1806
👩💻 Code package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
// 부분 합
public class BJ1806 {
static int n;
static int s;
static int[] arr;
static int length = Integer.MAX_VALUE;
static int start;
static int end;
static int total;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
s = Integer.parseInt(st.nextToken());
arr = new int[n];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < arr.length; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
while(true) {
if(total >= s){
length = Math.min(length, end - start);
total -= arr[start];
start++;
}
else if(end == n) break;
else {
total += arr[end];
end++;
}
}
if(length == Integer.MAX_VALUE) length = 0;
System.out.println(length);
}
}
💡 Learned 아이디어
package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
// 부분 합
public class BJ1806 {
static int n;
static int s;
static int[] arr;
static int length = Integer.MAX_VALUE;
static int start;
static int end;
static int total;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
s = Integer.parseInt(st.nextToken());
arr = new int[n];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < arr.length; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
while(true) {
if(total >= s){
length = Math.min(length, end - start);
total -= arr[start];
start++;
}
else if(end == n) break;
else {
total += arr[end];
end++;
}
}
if(length == Integer.MAX_VALUE) length = 0;
System.out.println(length);
}
}
💡 Learned 아이디어
Two-pointer
2つのポインタstart
およびend
を같은 방향
または반대 방향
に移動することが実現される.시간복잡도는 O(N)
Reference
この問題について([BOJ]1806部和), 我々は、より多くの情報をここで見つけました https://velog.io/@ssoyeong/BOJ-1806-부분합テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol