[백준 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해주면 된다.

 

코드