🔗 문제 링크
https://www.acmicpc.net/problem/1806
🤔 문제
10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.
😮 문제 해결 방법
아래의 그림과 같이 num 배열이 주어지고 다음 인덱스로 갈 때 마다 이전 값을 누적해서 더해주는 sum배열을 생성한다.
각 인덱스의 누적합을 더해준 sum배열의 동작에 대해 알아야한다.
예를 들어, sum 배열에서 인덱스 2에서 인덱스 6까지의 부분합을 구하고 싶다면, sum[6] - sum[2] = 25를 구할 수 있다. 이 결과가 성립할 수 있는 이유는 sum[2] = num[1] ~ num[2]까지의 합이고 sum[6] = num[1] ~ num[6] 까지의 합이기 때문에 sum[6] - sum[2] = (num[1] , num[2] ~ num[6]) - (num[1] ~ num[2]) 이런 식이 성립한다.
즉 num[3] ~ num[6] 까지의 합이 됨을 알 수있다.
해당 문제는 모든 부분합의 경우의 수를 확인하기 위해 투 포인터를 이용해 문제를 해결한다 .
- 왼쪽 포인터 부터 오른쪽 포인터까지의 부분합이 S 값보다 작은 경우
- 왼쪽 포인터 부터 오른족 포인터까지의 부분합이 S값보다 크거나 같은 경우
- 오른쪽 포인터가 마지막까지 이동한 후 왼쪽 포인터를 이동하면서 경우의 수를 다 비교하는 경우
1번의 경우는 부분합이 S 값보다 작기 때문에 부분합을 증가시켜 주어야한다. 문제에서 자연수라고 했기 때문에 오른쪽 포인터를 이동함으로써 부분합을 늘려줄 수 있다.
2번의 경우는 부분합이 S 값보다 크거나 같은 경우엔 정답 요건에 충족하기 때문에 길이를 비교해준 후 최소 길이이면 갱신을 해준다.
갱신을 해준 이후에는 현재 범위의 부분합보다 작은 부분합이 있는 경우를 비교해주어야 하기 때문에 왼쪽 포인터를 이동해 부분합을 줄여준다.
3번의 경우는 오른쪽 포인터가 마지막에 도달하는 경우에도 왼쪽 포인터가 마지막까지 이동하면서 남은 경우의 수를 모두 확인해야한다.
따라서, 부분합이 S 보다 크거나 같은 경우엔 길이를 비교한 후 왼쪽 포인터를 이동하고, S보다 작은 경우엔 답에 충족하지 않기 때문에 왼쪽 포인터만 이동 시켜준다.
🚩 Java 코드
package com.algorithm.Baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_1806_부분합 {
private static int[] num;
private static int[] sum;
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());
num = new int[N + 1];
sum = new int[N + 1];
st = new StringTokenizer(br.readLine());
for (int loop = 1; loop <= N; loop++) {
num[loop] = Integer.parseInt(st.nextToken());
sum[loop] = sum[loop - 1] + num[loop];
}
int rst = getLength(N, S);
System.out.println(rst);
br.close();
}
private static int getLength(int n, int s) {
int length = n + 1;
int left = 0, right = 0;
while(left <= n || right <= n) {
if(right <=n) {
// 1. 부분합이 찾고자 하는 값 보다 작으므로 부분합을 증가시켜야함
if (sum[right] - sum[left] < s) {
right++;
}
// 2. 부분합이 찾고자 하는 값 보다 크거나 같으므로 길이 비교후 부분합을 감소시켜야함
else {
length = Math.min(length, right-left);
left++;
}
}
// 3. 오른쪽 포인터가 마지막에 가도 왼쪽 포인터는 값을 끝까지 비교해줘야함
else {
if(sum[right-1] - sum[left] >= s) {
length = Math.min(length, right-left);
}
left++;
}
}
return length == n+1 ? 0 : length;
}
}