알고리즘
백준 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;
}
}