[C] 코드업 문제풀이 2631: 보물찾기

문제설명

수열 속에 숨어 있는 보물들을 찾아보자. nn개의 자연수로 이루어진 수열이 있다.

이 수열들 중 연속된 11개 이상의 원소들의 합이 정확히 kk가 되면 이 구간은 보물구간이라고 한다.

주어진 nn개의 자연수 중에서 보물 구간이 몇 개 있는지 구하는 프로그램을 작성하시오.

 

 

입력

첫 번째 줄에 자연수 nn과 kk가 공백으로 구분되어 입력된다.

두 번째 줄에 nn개의 각 원소가 공백으로 구분되어 입력된다.

[입력값의 정의역]

5<=n<=100,0005<=n<=100,000

각 원소는 1,0001,000이하의 자연수

 

 

출력

보물 구간의 수를 출력한다.

 

 

입력 예시

5 15

1 2 3 4 5

 

 

출력 예시

1

---

#include <stdio.h>
int main(void){
    int n,k;
    int temp,count=0,arr[100000];
    scanf("%d %d", &n, &k);
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    for(int i=0;i<n;i++){
        if(arr[i]>k) continue;
        temp=arr[i];
        if(arr[i]==k){
            count++;
            continue;
        }
        else{
            for(int j=i+1;j<n;j++){
                temp+=arr[j];
                if(temp>k) break;
                else if(temp==k){
                    count++;
                    break;
                }
            }
        }
    }
    printf("%d", count);
    return 0;
}

이건 배열로 풀어야 할지 기본 형태로 풀 수 있을지 고민하게 만들었다. 결과적으로는 배열이 가장 적당하다는 것!

이 이유는 바로 누적했다가 없애야 하는 과정이 있기 때문이다. 일반적으로 변수를 선언해 하면 이전 값으로 돌아갈 수 없다. 그렇기에 할 수 없다는 결론이 나오게 되었다. 값을 입력받아 저장하는 것까지는 많이 어렵지는 않다. 이제 count하는 과정이 중요한 것 같다. temp로 저장하는 것이 필요한데 그 이요는 기존 값을 변화시킬 수 없기 때문이다. 그래서 arr[i] 값이 크지 않는 이상 값 변화를 위해 temp로 저장해 준다.

그 다음에 같으면 count 해주는 것은 크게 어렵지 않다. else문도 조금 낮설다. j 값으로 하는데  이것을 이용해서 i 값을 다시 탐색해 해 주어야 한다. 기존에 누적하는 과정도 반복하고 그 안에서 다시 temp를 이용해 판단해주기 때문이다.

만약 값이 초과되면 중단되고 또다시 다른 탐색을 해줘야 하고, 같으면 count를 해서 마지막으로 출력해주면 된다.