백준 1806번 : 부분합 자바

🧫 문제 분석

 

✔️ 출처

부분합 골드 4

 

📖 문제

 

누적합 문제를 한번도 안풀어봐서 기본 개념을 익히고 풀어봤다. 

여기서는 투 포인터 알고리즘을 사용한다. 

 

시작 포인터 : start

끝 포인터 : end 

 

처음 start 와 end를 첫번째 요소 위치에 둔다.

end를 움직일때마다 해당 end에 값을 sum에 더하고 

그 값이 목푯값 s 이상인지 확인한다. <= 중요.. 이걸 제대로 안봐서 삽질했다. 

sum >= s 이면 end - start 와 기존 count 중 더 작은 값을 취한다.

 

 

 

 

 

 

 

---

🔅 문제 풀이

import java.io.*;
import java.util.*;

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 start = 1, end = 1;
        int sum = 0;
        int count = n;
        int[] arr = new int[n + 1];

        st = new StringTokenizer(br.readLine());

        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        boolean flag = false;
       
        while (true) {
            if (end >= arr.length  && sum < s) {
                break;
            }

            if (sum < s) {
                sum += arr[end++];

            } else {
                count = Math.min((end - start), count);
                sum -= arr[start++];
                flag = true;
            }
        }

        if (flag) {
            System.out.println(count);
        } else {
            System.out.println(0);
        }
    }
}

 

sum >= s 인데  sum - arr[start] , start++ 하는 이유

우선 sum이 목푯값 s에 도달하면 이 길이가 최댓값이 된다. 
예를 들어

N : 4  S : 5

1 2 3 4 

라고 하자 

 

필자의 코드대로면 

start : 1 

end  : 4 (end++ 후위 연산자 때문에)

길이 : 3 , sum = 6이다 

 

여기서 end 를 증가시키고 더해버리면 

길이가 4가 되어 현재 부분합의 최소 길이를 넘어가버린다. 

따라서 sum이 목푯값 sum 이 되면 

이 부분합의 길이를 최댓값으로 잡고 

sum - arr[start++] 를 하여서 목푯값을 만족하는 더 짧은 길이를 찾는다. 

 

---

리팩토링

import java.io.*;
import java.util.*;

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];
        int start = 1, end = 1; // 1번 부터 시작
        int sum = 0;
        int count = n + 1;

        st = new StringTokenizer(br.readLine());

        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        while (end < arr.length || sum >= s) {
            if (sum < s) {
                sum += arr[end++];

            } else {
                count = Math.min((end - start), count);
                sum -= arr[start++];

            }
        }

        System.out.println((count == n + 1) ? 0 : count);
    }

}

 

여러사람들의 코드를 보면서 내 코드를 더 단순하게 바꿔보았다.

 

 

 

 

 

 

❗ 오답노트 / 필요한 지식

1. 누적합이자 투 포인터에 대한 공부를 하게 되었으므로 잘 기억해두고 익히자
2. start, end를 0으로 할 경우 while문에서 end <= n 으로 바꾸면 된다.