BOJ13422 도둑

윤재에요 2024. 3. 5. 23:13

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

13422번: 도둑

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

www.acmicpc.net

누적합

import java.util.*;
import java.io.*;
public class Main
{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        
        while(T-->0){
            String[] input1 = br.readLine().split(" ");
            String[] input2 = br.readLine().split(" ");
            
            int n = Integer.parseInt(input1[0]);
            int m = Integer.parseInt(input1[1]);
            int k = Integer.parseInt(input1[2]);
        
            int[] money = new int[n];
            for(int i=0; i<n;i++){
                money[i] = Integer.parseInt(input2[i]);
            }
            int[] acc = new int[n+m];
            acc[0]=0;
            
            for(int i=1; i<n+m;i++){
                acc[i] = acc[i-1] + money[(i-1)%n] ;
            }

            
            if(m==n){
                
                if(acc[n]<k){
                    System.out.println(1);
                }else{
                    System.out.println(0);
                }
                continue;
            }

            
            
            int sum=0;
            int count=0;
            for(int i=m;i<n+m;i++){
                sum = acc[i]-acc[i-m];
                if(sum<k) count++;
            }
            System.out.println(count);
        }
	}
}

투포인터 슬라이딩 윈도우

import java.util.Scanner;

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[] money = new int[N];
            for (int i = 0; i < N; i++)
                money[i] = sc.nextInt();

            int currentSum = 0;
            for (int i = 0; i < M; i++)
                currentSum += money[i];

            int ans = (currentSum < K ? 1 : 0);
            if (N != M) {
                for (int i = 1; i < N; i++) {
                    currentSum -= money[i - 1];
                    currentSum += money[(i + M - 1) % N];
                    if (currentSum < K) ans++;
                }
            }
            System.out.println(ans);
        }
    }
}