[백준] 1806번 : 부분합 - C++ / JAVA

백준 1806 : 부분합

등급 : Gold IV

1806번: 부분합 (acmicpc.net)

1806번: 부분합

사용 알고리즘 : Two Pointer

사용 자료구조 : Vector

 

정렬되지 않은 배열에서의 합의 길이가 최소가 되는 길이를 구하는 문제이다.

Sum이 Target보다 크거나 같으면 Left를 늘려주고, Sum이 Target보다 작으면 Right를 늘려주는 방식으로 풀 수 있다.

 

---

  1. n값과 s값, n에 따른 배열 값을 입력받음.

  2. left, right, sum을 0으로, ans는 나올 수 있는 최댓값보다 큰 값을 넣고 투 포인터를 진행.

       ( 정렬이 되어있지 않으므로 앞에서부터 차례로 탐색. left와 right는 같이 0과 0으로 시작하므로 left <= right 조건으로 입력. )

       1) sum값이 s(target)값보다 크거나 같을 경우의 길이를 저장하고, 길이를 줄이기 위해 left값을 뺀 후 left를 증가시켜준다.

       2) sum값을 늘려야 하는 경우, right값을 늘려야 하는데 right가 이미 끝 좌표를 넘었다면 투 포인터를 종료하도록 한다.

          → 이는 right값을 sum에 추가시킨 후에 right를 증가시키기 때문이다. 현재 sum 값 : left ~ right - 1까지.

       3) 이후 sum 값을 늘려야 하므로 sum에 right값을 추가하고, right는 다음 위치를 가리키도록 증가시켜준다.

       ( 조건문 작업을 효율적으로 하기 위해 위와 같은 순서가 강제된다. 순서가 바뀔 경우 조건문을 수정해야 한다. )

  3. 투 포인터를 종료했을 때 ans값이 그대로라면 가능한 최소 길이가 없는 것이므로 0을 출력. 그렇지 않을 경우 ans 출력.

---

<hide/>
#include <iostream>
#include <vector>

using namespace std;
#define INF 2e9

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, s;
    cin >> n >> s;
    vector <int> v(n, 0);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    int left = 0;
    int right = 0;
    int sum = 0;
    int ans = INF;
    while (left <= right)
    {
        if (sum >= s)
        {
            ans = min(ans, right - left);   
            sum -= v[left];
            left++;
        }
        else if (right == n) break;
        else
        {
            sum += v[right];
            right++;
        }
    }
    if (ans == INF) cout << 0;
    else cout << ans;
}

<hide/>
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;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        List<Integer> v = new ArrayList<>();
        for(int i=0; i<n; i++)
        {
            v.add(Integer.parseInt(st.nextToken()));
        }
        int left = 0;
        int right = 0;
        int sum = 0;
        int ans = (int)2e9;
        while(left <= right)
        {
            if(sum >= s)
            {
                ans = Math.min(ans, right - left);
                sum -= v.get(left);
                left++;
            }
            else if(right == n) break;
            else
            {
                sum += v.get(right);
                right++;
            }
        }
        if(ans == (int)2e9) System.out.println(0);
        else System.out.println(ans);
    }
}