[Gold IV] 부분합 - 1806
성능 요약
메모리: 22944 KB, 시간: 220 ms
분류
누적 합(prefix_sum), 두 포인터(two_pointer)
문제 설명
10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
출력
첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.
풀이
투포인터 알고리즘은 처음 접해서 찾아보았다
https://ssungkang.tistory.com/entry/Algorithm-Two-Pointers-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0
투포인터 알고리즘 : 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘
start와 end라는 두 index를 두고 결과값에 따라 index를 조정하며 결과를 얻는 것이다.
이 문제에서는 누적합을 저장하는 배열을 구한 후, start와 end 모두 0(여기선 1)에서 시작하여 값을 구한다
부분합이 S 이상인 수열 중 길이가 가장 짧은 것을 구해야 하니까 sum이 S이상인 경우 그 길이와 ans를 비교해서 더 작은 값을 ans로 업데이트하고, start를 1 증가하였다.
sum이 S보다 작은 경우에는 end를 1 증가하여 부분합이 증가할 수 있도록 하였다.
이렇게해서 배열을 끝까지 (end가 N 이하일 때까지) 훑고 나면 최소의 길이를 구할 수 있다.
합을 만드는 것이 불가능한 경우에는 답을 0으로 바꿔 출력하였다
package BOJ.Gold.g4;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ_1806_부분합 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int S = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int[] arr = new int[N+1]; // 누적합 저장
for (int i=1; i<=N; i++)
arr[i] = arr[i-1]+Integer.parseInt(st.nextToken());
// 투포인터
int start = 1;
int end = 1;
int ans = 100001;
while (start<=end && end<=N) { // 종료 조건 : 배열의 끝까지 훑은 경우
int sum = arr[end]-arr[start-1]; // start~end까지의 누적합
if (sum>=S) {
ans= Math.min(ans, end-start+1); // sum이 S 이상인 경우 길이 update
start++; // start를 증가시켜 더 작은 길이가 가능한지 검사
}
else end++; // sum이 S 미만인 경우 end++
}
if (ans==100001) ans=0;
System.out.println(ans);
}
}
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 16946 - 벽 부수고 이동하기 4 (자바 Java) (0) | 2022.11.01 |
---|---|
[백준] 1644 - 소수의 연속합 (자바 Java) (0) | 2022.10.30 |
[백준] 1987 - 알파벳 (자바 Java) (0) | 2022.10.28 |
[백준] 17143 - 낚시왕 (자바 Java) (0) | 2022.10.26 |
[백준] 12015 - 가장 긴 증가하는 부분 수열 2 (자바 Java) (0) | 2022.10.25 |