[백준] 21921번 : 블로그 - JAVA [자바]

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

 

---

문제

 

 

위 문제는 N이 250,000 이하의 값을 가지기 때문에 O(N*N) 형식의 완전탐색으로 푼다면 시간 초과가 걸릴 것이다.

X의 기간은 항상 값을 유지하기 때문에 이를 슬라이딩 윈도우 아이디어로 풀면 되겠다는 생각을 했다.

 

X의 값만큼의 윈도우를 설정하고 한칸씩 밀어버리는 방법이다.

이렇게 푼다면 O(N)으로 풀 수 있다.

 

윈도우 범위와 인덱스의 위치등 값만 신경써서 해주면 된다.

 

---

전체 코드

public class Main {
	
    public static void main(String[] args) throws Exception {
    	System.setIn(new FileInputStream("./input.txt"));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuilder sb = null;
        
        st = new StringTokenizer(in.readLine());
        
        int N = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(in.readLine());
        
        int[] arr = new int[N + 1];
        int total = 0;
        
        for(int i = 1; i <= N; i++) {
        	int num = Integer.parseInt(st.nextToken());
        	arr[i] = num;
        	
        	if(i <= X) {
        		total += num;
        	}
        }
        
        int MAX = total;
        int count = 0;
        
        if(MAX != 0) {
        	count++;
        }
        
        for(int i = 2; i <= N - X + 1; i++) {
        	
        	total -= arr[i - 1];
        	total += arr[i + X - 1];
        	
        	if(MAX < total) {
        		count = 1;
        		MAX = total;
        	}
        	else if(MAX == total){
        		count++;
        	}
        }
        
        
        
        if(MAX == 0) {
        	System.out.println("SAD");
        }
        else {
        	System.out.println(MAX);
            System.out.println(count);
        }
        
        
    }
}

---

결과