알고리즘

백준 13422번 도둑 (JAVA)

박카스마시며코딩 2022. 9. 17. 18:32

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

 

13422번: 도둑

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 마

www.acmicpc.net

 

저는 슬라이딩 윈도우를 통해 문제를 해결하였습니다.

입력 배열을 m-1개 더 늘려 n개 뒤에 m-1개 만큼 입력을 다시 넣었습니다.

슬라이딩 윈도우를 통해 m 간격의 합을 구하고 이 값이 k보다 작다면 결과값을 늘렸습니다.

하지만, n과m이 같으면 이렇게 구하면 중복이 나오기 때문에 n == m일때 예외 처리하여 문제를 해결하였습니다.

 

package BOJ.twopoint;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_13422 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Function<String,Integer> stoi = Integer::parseInt;
        int testCnt = stoi.apply(st.nextToken());
        for(int t = 0 ; t < testCnt ; t++){
            st = new StringTokenizer(br.readLine());
            int n = stoi.apply(st.nextToken());
            int m = stoi.apply(st.nextToken());
            int k = stoi.apply(st.nextToken());
            int[] input = new int[n+m-1];
            st = new StringTokenizer(br.readLine());
            for(int i = 0 ; i < n ; i++){
                int num = stoi.apply(st.nextToken());
                input[i] = num;
                if(i < m-1 ){
                    input[n+i] = num;
                }
            }
//            System.out.println(Arrays.toString(input));
            int result = cal(input,n,m,k);
            System.out.println(result);
        }
    }

    private static int cal(int[] input, int n, int m, int k) {
        int result = 0;
        int sum = 0;
        for(int i = 0 ; i < n+m-1 ; i++){
            sum += input[i];
            if(i >= m){
                sum -= input[i-m];
            }
            if(i >= m-1 && sum < k){
                result++;
            }
            if(i == m-1 && n == m){
                break;
            }

        }
        return result;
    }
}