문제

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

설명

문제푼 기간만 대략 3 일이나 걸렸다. 그마져도 바빠서 미루다가 겨우 풀었다. 처음에는 무지성으로 이중 for문을 이용하여 부분합의 경우의 수를 구하도록 하였으나 문제의 핵심 조건은 제한시간이였다. 무지성으로 이중 for문을 이용해 결과를 도출하려고 하면 테스트 케이스의 길이가 길어질수록 걸리는 시간도 기하 급수적으로 늘어날 수 밖에 없다. 따라서 다른 더 효율적인 알고리즘을 이용하여야 했는데 여기서 필요한 알고리즘이 바로 투 포인터 알고리즘이었다. 투포인터 알고리즘이란 말그대로 포인터(커서)가 두개라는 의미이며 수열이 있을때 두포인터를 모두 0 번째 배열을 가리키도록하고 포인터 사이에 있는 모든 요소의 합과 목표하는 값을 비교하여 두 포인터의 위치를 조정하여 부분합의 길이를 구하는 것이다.(https://butter-shower.tistory.com/226) 이것을 이용하여 이 문제를 풀 수 있었다. 일단 n(수열의 길이) s(목표하는 값)을 입력받고 수열 원소를 입력 받은다음 위에서 말한 투 포인터 알고리즘을 활용하기 위해서 temp변수에 초기값인 수열에서 0 번쨰 수를 넣고 그다음 두 포인터 사이에 요소를 더한 값이 목표값보다 작으면 오른쪽 포인터를 한칸 오른쪽으로 이동시키고 크거나 같으면 왼쪽 포인터를 이동하도록하였다. 그리고 왼쪽 포인터가 움직이는 상황이 온다는 것은 곧 최소한 목표한 값을 만들 수 있는 부분합이 최소 한개는 존재하는 것이므로 존재여부를 저장하는 변수 exist 변수의 값을 1(있음)으로 수정한다. 그리고 최종적으로 오른쪽 포인터가 수열의 끝에 다다르고, 더이상 두포인터 사이의 값이 목표값에 도달하지 않는 상태가 되면 바로 반복문을 그만두고 빠져나오도록하였으며 최종적으로 exist값이 0 이면 부분합 최소길이 (result_len)의 값을 0 으로, 해당사항이 없다면 최소길이를 그대로 출력하도록하였다. 최소길이는 위 반복문에서 두포인터의 부분합이 목표값보다 크거나 같게되는 순간의 부분합길이를 기존에 구해진 최소 부분합 길이와 비교하여 갱신되도록 하였다. 이문제를 통해 코딩은 역시 끈기, 즉 엉덩이가 무거워야함을 다시금 깨달았고 또 본격적인 코딩 실력의 향상을 위해서는 알고리즘 공부를 등한시하고 무식한 알고리즘을 사용하면 안된다는 것을 몸소 체험하게 되었다.

코드

#include <stdio.h>

int main() {
   // 1806 부분합 - GOLD IV 🥇
    int n,s,array[100000];
    scanf("%d %d",&n,&s); // 원소 갯수 / 목표 부분합
    for(int i=0; i<n; i++)  //수열 원소 하나씩 입력
        scanf("%d",&array[i]);
    int temp = array[0]; //두포인터(시작,끝)의 초기값 셋팅을 위해 배열 0번째값 추가
    int end=0,start=0,result_len=n,exist=0;
   while(1)
   {
       if(temp < s)
       {
           if(end  == n-1)
           {
               break;
           }
           else
           {
               end++;
               temp += array[end];
           }
       }
       else if(temp >= s)
       {
           if(exist == 0)
               exist = 1;
           if(result_len > end-start+1)
               result_len = end-start+1;
           temp -= array[start];
           start++;
       }
   }
    if(exist == 0)
        result_len = 0;
    printf("%d",result_len);
    return 0;
}