[C/C++] 코드업(codeup) 2631번 보물 찾기

▽문제 바로가기

https://codeup.kr/problem.php?id=2631

보물 찾기

---

입력

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

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

[입력값의 정의역]

5<=n<=100,000
각 원소는 1,000이하의 자연수

 

출력

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

 

문제 풀이

 

구간 탐색을 잘해야 하는 문제입니다.

 

[0]	[1]	[2]	[3]	[4]
↑i, ↑j

처음 sum = [0]인 상태입니다.

 

구간 합 15를 찾아야 한다면 15 이상의 값이 될 때까지 j인덱스를 증가시켜 주면 됩니다. 인덱스 범위의 합을 계속 증가시켜나갑니다.

 

[0]	[1]	[2]	[3]	[4]
↑i	↑j

sum = [0] + [1]

 

[0]	[1]	[2]	[3]	[4]
↑i		↑j

sum = [0] + [1] + [2]

 

만약, [0] + [1] + [2]의 합이 15 이상이라면 이제 i인덱스를 증가시켜주면 됩니다. 인덱스 범위의 합이 15 이하일 때까지 줄여나갑니다.

 

[0]	[1]	[2]	[3]	[4]
	↑i	↑j

sum = [1] + [2]

 

이런 과정에서 구간의 합이 15라면 count 해주면 됩니다.

 

#include <stdio.h>

int main() {
    
    int a, b;
    scanf("%d%d", &a, &b);
    int arr[a+1]={0};
    for(int i=0;i<a;i++) scanf("%d", &arr[i]);
    
    int i=0, j=0, sum=arr[0], count=0;
    for(;i!=a-1;){
    	//j인덱스가 끝에 도달했으면 i만 움직입니다.
    	if(j>=a-1){
    		sum-=arr[i++];
    		if(sum==b) ++count;
    		continue;
    	}
	//sum이 b보다 작으면 j를 움직입니다.
    	if(sum<b){
			sum+=arr[++j];
    	}
	//sum이 b보다 크면 i를 움직입니다.
    	if(sum>b){
    		sum-=arr[i++];
    	}
	//sum이 b랑 같으면 count를 세고 j를 움직입니다.
    	if(sum==b){
    		++count;
		sum+=arr[++j];
    	}
    }
    
    printf("%d", count);
        
    return 0;
}