백준 1806 - 부분합 (자바 JAVA)

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

1806번: 부분합

 

 

문제를 잘못읽어서 한시간동안 뻘짓하다가 통과되었습니다...

 

처음 문제를 봤을 때 부분합이 특정 숫자랑 일치하는 배열의 갯수를 구하는건줄 알고 풀었는데

계속 오답이 나서 다시 문제를 꼼꼼하게 읽어보니 특정 숫자(S로 주어짐) 이상인 배열 중에서

가장 짧은 배열의 길이를 구하는 거였네요... 

 

오늘의 교훈 : 문제를 꼼꼼하게 읽자!

 

  - 투포인터로 구간합을 각각 구해주면서 S보다 큰지를 체크해줬습니다. 아래코드에서 저는 부분합의 값이 S보다 큰경우, S와 일치하는 경우, S보다 작은 경우 이렇게 3가지 경우를 분리해서 짰는데(문제를 잘못 읽어서..) 전혀 그럴필요가 없고 S 이상인 경우와 S보다 작은경우 2가지 케이스만 생각해서 알고리즘 구현하면 됩니다. 

-  코드를 더 깔끔하게 수정할 수는 있겠지만 그냥 귀찮아서 올립니다. 제 코드는 참고만 하세요.

 

 

import java.io.*;
import java.util.*;
 
public class test {
 
    static int N;
    static long S;
    static int [] arr;
 
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        S = Long.parseLong(st.nextToken());
 
        arr = new int[N+2];
 
        st = new StringTokenizer(br.readLine());
 
        for(int i=1; i<=N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        int result = Integer.MAX_VALUE;
 
        // 투포인터 알고리즘 구현
 
        int left, right, sum;
        left = 1; // 왼쪽 포인터
        right = 1; // 오른쪽 포인터
        sum = arr[left];
        while(left!=N+1 && right!=N+1){
//            System.out.println("<left : " + left + "> <right : " + right + "> <sum : " + sum + ">");
            if (S == sum) { // sum값이 S와 일치하는 경우
                result = Math.min(result, right-left+1);
                // result++;
                if (right < N+1) {
                    right++;
                    sum += arr[right];
                }
 
            }else if (S < sum) { // sum값이 S보다 큰 경우
                result = Math.min(result, right-left+1);
                sum -= arr[left];
                left++;
                if (left > right) {
                    right = left;
                    sum = arr[left];
                }
            }else{ // sum값이 S보다 작은 경우
                right++;
                sum += arr[right];
            }
        }
        // 구현완료
 
        if (result == Integer.MAX_VALUE) result = 0;
        System.out.println(result);
 
 
    }
}