코드업(codeup) 2631 : 보물 찾기 C언어

▶문제 : 보물찾기 (codeup.kr)

보물 찾기

 

▶코드 작성

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n, k, i, L;
    int cnt = 0, sum;
    int *arr;

    scanf("%d %d", &n, &k);

    arr = (int *)malloc(sizeof(int) * n);

    for (i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }

    sum = arr[0];//더한 수들의 합
    L = i = 0;//L은 왼쪽 i는 오른쪽
    while (i < n)//i가 더이상 오른쪽으로 못갈 때 마무리
    {
        if (sum == k)//값이 같을 때
        {
            cnt++;
            sum -= arr[L];//맨 왼쪽값을 뺀다
            L++;//오른쪽으로 한칸 이동
        }
        else if (sum < k)//값보다 작을 때
        {
            i++;//오른쪽으로 한칸 이동
            sum += arr[i];//맨 오른쪽값을 더한다
        }
        else if (sum > k)//값보다 클 때
        {
            sum -= arr[L];//맨 왼쪽값을 뺀다
            L++;//오른쪽으로 한칸 이동
        }
    }

    printf("%d", cnt);

    free(arr);

    return 0;
}

 

▶해석

구하려는 값(k)과 가깝도록 sum을 유지시켜 조금씩 i가 n에 가깝게 이동하며 k값과 같은 값을 찾음