[백준 알고리즘 자바]1806 : 부분합

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을 출력하면 된다.

입출력 예제

---

항상 조건 한두개처럼 마무리를 못해서 혼자 해결을 못하네..

풀이 방식을 정리해보자.

 

1. BufferedReader 와 StringTokenizer 를 사용해서 변수 N, S, 배열 arr 을 입력받는다.

BufferedReader 와 Bufferedwriter (tistory.com) 참조

• BufferedReader : 입력된 데이터를 바로 전달하지 않고 버퍼에 저장해두었다가 전달하는 방법
• StringTokenizer : 하나의 문자열을 여러 개의 토큰으로 분리하는 클래스
• br.readLine() : 공백 기준으로 문자열을 나눈다.
• st.nextToken() : 다음 토큰을 불러오는 메서드
• 한 줄에 2개의 숫자를 입력받고 이를 공백을 기준으로 해서 각각 다른 값으로 다른 변수에 저장하기 위한 작업이다.

2. 최소 길이를 출력하기 위해 필요한 변수들을 선언한다.

• lt : 시작 포인터
• rt : 끝 포인터
• sum : lt와 rt의 합
• min : 최소 길이를 비교하기 위한 변수
• MAX_VALUE : 2의 31제곱인 (2,147,483,648)로 초기화해준다.

3.  lt <= N && rt <= N 조건을 넣은 while문을 선언한다.

• lt와 rt가 모두 수열의 끝까지 도달하면 멈추기 위해서이다.

4. 맨 처음 상태는 다음과 같다.

5. 여기에서  sum이 S 값인 15보다 작으므로 sum에 arr[rt] 값이 더해지고, rt는 1씩 증가한다.

6. 이제 sum 값이 S보다 커졌으므로 rt-lt와 min 값을 비교하고 sum에서 arr[lt] 값을 뺀 후에 lt가 1씩 증가한다.

7. 원하는 결과가 나왔으면 min과 MAX_VALUE 를 비교해서 맞으면 0, 아니면 min 값을 출력한다.

 

수행 결과를 확인한다.

답안 소스

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

public class Main {	
	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());
		
		int[] arr = new int[N+1];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int lt = 0;
		int rt = 0;
		int sum = 0;
		int min = Integer.MAX_VALUE;
		
                while(lt <= N && rt <= N) {

                    if(sum < S) {
                        sum += arr[rt++];
                    } else if(sum >= S) {
                        min = Math.min(min, rt-lt);
                        sum -= arr[lt++];
                    }
                }
        	System.out.println(min == Integer.MAX_VALUE ? 0 : min);
	}
}