[백준 13422] 도둑

 

예제를 예로 설명해보겠다.

 

입력값 배열

3

4

7

5

6

4

2

9

 

입력값따로, 부분합배열을 따로 만들어준다.

 

부분합 배열

3

7

14

19

25

29

31

40

43

47

for(int i=1; i<n+m; i++)
    psum[i] = psum[i-1] + a[(i-1)%n];

점화식은 위와 같다.

만약 7번 집부터 3개를 탐색해야 한다면 7, 8, 1 번 집을 탐색해야 하므로 입력값 배열의 첫번째를 확인해 주어야 한다.

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int t = sc.nextInt();
        while(t-->0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int k = sc.nextInt();
            int a[] = new int[n];
            for(int i=0; i<n; i++)
                a[i] = sc.nextInt();
            int psum[] = new int[n+m];
            for(int i=1; i<n+m; i++)
                psum[i] = psum[i-1] + a[(i-1)%n];
            
            int cnt = 0;
            
            if(n == m) {
                if(psum[n] < k) cnt++;
            } else {
                for(int i=m; i<n+m; i++)
                    if(psum[i] - psum[i-m] < k)
                        cnt++;
            }
            System.out.println(cnt);
        }
    }
}