[BOJ 백준] 부분합(1806) Java

링크 : https://www.acmicpc.net/problem/1806

1806번: 부분합

 

문제 설명 : 

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

 

입력 : 

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

 

출력 : 

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

예제 입력 : 

10 15
5 1 3 5 10 7 4 9 2 8

 

예제 출력 : 

2

 

 

접근법 : 

1) 어떻게 풀 것인가?

부분합을 매번 구하게 되면 N^2의 시간복잡도가 발생해 시간초과가 발생한다.

 

부분의 합이 연속된 수라고 고정되있으므로, 조건을 충족할 경우 출발점을 당기면서 끝점을 늘리는 형태로 알고리즘을 구현하면된다. (투포인터 또는 슬라이딩 윈도우)

 

헷갈릴경우

① 임시합 > S 일때 Start Point와 End Point를 어떻게 할지. 

② 임시합 == S 일때 Start Point와 End Point를 어떻게 할지.

③ 임시합 < S 일때 Start Point와 End Point를 어떻게 할지.

생각해보면 좋다.

 

2) 시간복잡도

10만의 숫자를 N번 보면서 for문으로 시작점을 당기므로 대략 O(N) (상수 * N 정도 발생)

(Java 기준 -  232ms)

 

3) 공간복잡도

N이 10만인 int 배열을 만들면 되므로 여유있음.

 

4) 풀면서 놓쳤던점

임시합이 < S일때, start pointer에 +1 처리를 안해줘서 오답 발생.

 

5) 이 문제를 통해 얻어갈 것

투 포인터 기본적 활용.

for문 이중 loop 방식, while문 if문으로 양쪽으로 pointer 이동 둘 다 연습.

 

C++ 코드 : 

// 부분합 1806 C++
#if 1
#pragma warning(disable:4996)
#include <cstdio>

#define IMPOSSIBLE (100001)

using namespace std;

int N, S;
int array[100000 + 3];

int low;					// 슬라이딩 윈도우 출발점
int sum;					// 슬라이딩 윈도우 합
int ans;					// ans : 정답

int main() {

	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &N, &S);
	ans = IMPOSSIBLE;
	sum = low = 0;

	for (int i = 0; i < N; i++) {
		// 1. array 입력받으면서 합을 더함
		scanf("%d", &array[i]);
		sum += array[i];

		// 2. 합이 목표합보다 크거나 같을 경우 
		// 시작점을 당김 (low를 오른쪽으로 이동)
		if (sum >= S) {
			// 2-1. 최소 개수를 찾기 위해 출발점에 1을 더하면서 답과 비교
			for (int j = low; j <= i; j++) {
				// 당긴 값과 답을 비교
				if (ans > (i - j + 1)) ans = i - j + 1;
				// 답 갱신을 위해 임시합에서 값을 빼줌
				sum -= array[j];
				// 임시합이 목표합보다 작아졌을 경우 end point를 늘리기 위해 break
				if ( sum < S) {
					low = j + 1;
					break;
				}
			}
		}
	}

	if (ans == IMPOSSIBLE) ans = 0;
	printf("%d", ans);

	return 0;
}

#endif

 

Java 코드 : 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

// 부분합 백준 1806
public class Main {
	
	static int N, S;				// N 숫자 개수, S 목표합
	static int[] array;				// 입력받은 배열
	static int sp, tmpSum, ans;		// sp 시작점, ep 끝점, tmpSum 임시합, ans 갯수
	
	static final int IMPOSSIBLE = 100001;	// 불가능한 값 = 초기값
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// N, S 입력
		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		
		// 초기값 세팅
		sp = tmpSum = 0;
		ans = IMPOSSIBLE;
		array = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for (int i=0; i<N; i++) {
			// 1. 입력받으면서 array 배열에 넣고 임시 합을 더함
			array[i]= Integer.parseInt(st.nextToken());
			tmpSum += array[i];
			
			// 2. 임시합이 목표합보다 크거나 같을 경우 시작점을 당김
			if (tmpSum>=S) {
				// 2-1. 최소 개수를 찾기 위해 출발점에 1을 더하면서 답과 비교
				for(int j=sp; j<=i; j++) {
					// 당긴 값과 답을 비교
					if (ans > (i-j+1)) ans = i-j+1;
					// 답 갱신을 위해 임시합에서 값을 빼줌
					tmpSum -= array[j];
					// 임시합이 목표합보다 작아졌을 경우 end point를 늘리기 위해 break
					if (tmpSum<S) {
						sp = j+1;
						break;
					}
				}
			}
		}
		// 불가능할 경우  ans를 0으로 갱신
		if(ans == IMPOSSIBLE) ans = 0;
		bw.write(String.valueOf(ans)+"\n");				

		bw.flush();
		bw.close();
		br.close();
	}
}