[백준 1806번] 부분합 - java

문제 설명

1. 전체 숫자 N, 만들어야 하는 숫자 S가 주어진다.

2. N개의 숫자가 주어지고 숫자는 순서대로 더할 수 밖에 없다

3. S를 만들 수 있는 최소한의 숫자 개수를 return한다. 만약 만들지 못하면 0을 return한다.

 

 

풀이 과정

 1. 연속된 순서를 구하는 방법은 다음과 같다.

  - 0번 인덱스부터 수를 더해 합이 S가 될 때까지 진행한다.

  - 숫자의 합이 S가 되면 지금까지 더한 숫자의 맨 앞 인덱스를 지우고 다시 판단한다.

  - 숫자를 뺀 뒤에도 S보다 숫자의 합이 더 크면 이전 단계를 다시 진행한다.

  - S보다 작아진 경우, 다음 인덱스를 더해 준다.

 2. 이 방식을 통해 구할 수 있을 것이다.

 3. 예를 들어 10 글자로 15를 만들려 한다면 

   ex ) - N = 10, S = 15

         - 5 1 3 5 10  7 4 9 2 8 -> 순서대로 0, 1, 2, ....9, 10번 인덱스

        01) sum=05, S=15    ->    길이 1,  맨 앞 인덱스 0,  다음에 확인할 인덱스 1   X

        02) sum=06, S=15    ->    길이 2,  맨 앞 인데스 0,  다음에 확인할 인덱스 2   X

        03) sum=09, S=15    ->    길이 3,  맨 앞 인데스 0,  다음에 확인할 인덱스 3   X

        04) sum=14, S=15    ->    길이 4,  맨 앞 인데스 0,  다음에 확인할 인덱스 4   X

        05) sum=24, S=15    ->    길이 5,  맨 앞 인데스 0,  다음에 확인할 인덱스 4   O

        06) sum=19, S=15    ->    길이 4,  맨 앞 인데스 0,  다음에 확인할 인덱스 4   O

        07) sum=18, S=15    ->    길이 3,  맨 앞 인데스 0,  다음에 확인할 인덱스 4   O

        08) sum=15, S=15    ->    길이 2,  맨 앞 인데스 0,  다음에 확인할 인덱스 4   O

        09) sum=10, S=15    ->    길이 1,  맨 앞 인데스 0,  다음에 확인할 인덱스 4   X

        00) sum=17, S=15    ->    길이 2,  맨 앞 인데스 0,  다음에 확인할 인덱스 5   O

        01) sum=07, S=15    ->    길이 2,  맨 앞 인데스 0,  다음에 확인할 인덱스 5   X

        02) sum=11, S=15    ->    길이 2,  맨 앞 인데스 0,  다음에 확인할 인덱스 5   O

 

..........이런 식으로 구해주면 될 것이다.

추가로 만약 sum을 끝까지 구하지 못하면 0을 return해주면 된다.

 

코드

	import java.util.*;
	public class Main {
	public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
	long S = sc.nextLong();
	// 합 sum
	long sum = 0;
	// 해당 sum을 만들때 들어간 숫자의 개수 length
	int length = 0;
	// 최소값 min
	int min = N;
	// 주어진 숫자로 S를 만들 수 있으면 make는 true
	boolean make = false;
	// 입력 개수 N+1개. 딱 배열이 끝날 떄 sum을 완성하는 경우 문제 발생 가능성을 없애기 위해 +1을 해 주었다.
	int input[] = new int[N+1];
	for(int i=0; i<N; i++)
	input[i] = sc.nextInt();
	for(int i=0; i<N+1; i++) {
	// 현재 합 sum이 S보다 작은 경우 숫자를 더해주고 길이가 늘어난다.
	if(sum < S) {
	sum += input[i];
	length++;
	}
	else { // 길이가 같은 경우 맨 앞의 숫자를 뺴준다.
	make = true; // 주어진 숫자로 S를 만들 수 있다.
	min = Math.min(min, length); // 최소의 길이를 매번 판별해 준다.
	sum -= input[i-length]; // 맨 앞을 빼준다.
	length--; // 길이가 줄어든다.
	i--; // 해당 배열을 다시 확인 가능하도록 process를 이전으로
	}
	}
	// 주어진 숫자들로 못만들면 0을 return
	if(!make) min = 0;
	System.out.println(min);
	}
	}

view raw 부분합 hosted with ❤ by GitHub