[JAVA] 백준 1806. 부분합 :: 로직/코드 - GODZ

안녕하세요 GODZ입니다.

오늘은 이분 탐색과 투 포인터를 이용한 문제를 풀어볼 예정입니다.

---

1. 문제

사진을 클릭하면 문제 페이지로 이동합니다

 

2. 입출력 예제

 

3. 접근

1. N개의 수를 하나씩 입력 받으면서 합 sum을 구한다.

2. sum >= S 일 때, 길이 len을 저장하고 0번 인덱스부터 S보다 작아질 때까지 sum에서 뺀다.

3. sum < S 일 때, 다시 입력 받으면서 sum에 더한다. sum >= S 일 때, 2번 작업 반복.

4. 모든 수를 다 입력 받았으면 저장한 길이 len 중 최소값을 찾는다.

5. 만약 저장한 길이 len이 존재하지 않는다면 0을 출력한다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    final static int MAX = 100001;
    static int N;    // 배열 크기
    static int S;    // 목표값
    static int[] nArr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        
        int len = 0;
        int sum = 0;
        int startIdx = 0;
        int res = MAX;
        nArr = new int[N];
        st = new StringTokenizer(br.readLine().trim());
        for(int i = 0; i < N; i++) {
            nArr[i] = Integer.parseInt(st.nextToken());
            sum += nArr[i];
            len++;
            if(sum >= S) {
                while(true) {
                    if (sum >= S) {
                        res = Math.min(len, res);                    
                        sum -= nArr[startIdx];
                        startIdx++;
                        len--;
                    } else {
                        break;                        
                    }
                }
            } 
        }
        res = (res > 100000) ? 0 : res;
        System.out.println(res);
    }
}
 

 

5. 결과

 

 

 

[추가]

* 입력받는 수가 최대 100,000개 이므로 res를 100,001로 설정했다. sum >= S를 한 번도 만족하지 못했다면 line 41에서 res가 0이 된다.

 

* startIdx는 sum >= S 일 때, 앞에서(0) 부터 빼는 인덱스를 변수로 설정한 것이다.