1806번

https://www.acmicpc.net/problem/1806

1806번: 부분합

오늘 푼 문제는 누적합과 투 포인터를 이용하는 문제였다. 나는 이 문제의 접근방식은 맞았지만 구현하는 과정에서 조건문을 처리하는 것에서 문제가 있어서 애를 먹었다.. 또 감자 짓도 해서 문제를 잘못 읽어 S인 값을 찾는다고 생각해버렸다.. 하지만 문제에는 S이상인 값이었다...

어쨌든 그래서 이 문제의 풀이 방법을 설명해보면 슬라이딩 윈도우 알고리즘이라고 생각하면 된다. 물론 슬라이딩 윈도우는 정해진 칸을 옮기는 것이지만 같은 원리로 옮기는 칸을 두개의 점으로 생각하면 된다. 즉, 투 포인터 알고리즘이다.

 

시작점과 끝점을 둘다 인덱스 0에 두고 시작한다. 그리고 누적합이 S보다 크면 시작점을 움직이고, S보다 작으면 끝점을 움직인다.

처음 시작은 주어진 S가 0이 아닌 이상 당연히 끝점이 움직인다. 또한 0인 경우는 수열에 0이 없다면 반환을 0으로 한다.

 

그래서 이 방식으로 탐색을 진행하면서 제일 짧은 거리를 계산한다.

투 포인터 알고리즘을 알고 있다면, 조건만 잘 짜낸다면 쉽게 해결 할 수 있을 것이다.

주의 할 점은 끝점이 N-1인 경우에도 탐색이 진행되어야 한다는 것이다.

예를 들어 10 10 /n 1 1 1 8 10으로 주어진다면 출력값이 1이 나와야한다.

하지만 만약 반복 조건을 끝점!=N이라고 주면 출력 값이 3으로 나올 것이다.

그 이유는 끝점의 위치를 마지막에 증가시켜서 1 1 8로 계산할 때 끝점의 위치는 10의 위치에 가있기 때문이다.

그래서 N-1의 위치 또한 확인하려면 끝점!=N의 조건을 주면 안된다.

 

그래서 정답 코드는 아래와 같다.

package backjoon.b1806;

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

public class b1806 {
    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());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for(int i=0; i<N; i++){
            arr[i]= Integer.parseInt(st.nextToken());
        }
        int left = 0;
        int right = 0;
        int sum = 0;
        int count = Integer.MAX_VALUE;
        while (true) {
            if (sum>=S) {
                if (count > right - left) {
                        count = right - left;
                }
                sum-=arr[left++];
            }
            else if (right==N) {
                break;
            }
            else {
                sum += arr[right++];
            }
        }

        if(count!=Integer.MAX_VALUE){
            System.out.println(count);
        }else System.out.println(0);
    }
}