[Java] 백준 풀기 21921 - 블로그

자바 백준 21921번

실버 3

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

21921번: 블로그

 

 

 

 

 

문제 보기

분류: 누적 합, 슬라이딩 윈도우

 

 

 

 

 

문제 풀기

for loop을 이용하여 구간 합을 찾을 경우 `시간초과`가 발생한다.

시간 초과를 해결하기 위해 for loop을 사용하지 않고 다이나믹 프로그램을 이용하여 이미 계산된 날짜별 누적 합에서 필요한 날짜 구간만큼의 index 차이를 통해 결과를 얻는다.

구간마다 총 방문자를 계산하여 최대 방문자를 넘을경우 이를 새로 갱신하고 같은 경우 그 횟수를 증가시킨다.

 

 

 

 

 

코드 보기

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 블로그 시작부터 지난 일수와 X일 동안의 기간 입력 받기
        int N = sc.nextInt();  // 블로그 시작부터 지난 일수
        int X = sc.nextInt();  // X일 동안의 기간
        
        // 각 날짜별 방문자 수 입력 받기
        int[] visitors = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            visitors[i] = sc.nextInt();
        }
        
        
        // 최대 방문자 수와 해당 기간을 계산하는 함수 호출
        int[] result = findMaxVisitors(visitors, N, X);
        
        // 결과 출력
        if (result[0] == 0) {
            System.out.println("SAD");
        } else {
            System.out.println(result[0]);
            System.out.println(result[1]);
        }
    }
    
    // 최대 방문자 수와 해당 기간을 계산하는 함수
    static int[] findMaxVisitors(int[] visitors, int N, int X) {
        // 각 날짜별 누적 방문자 수 계산 (다이나믹 프로그래밍)
        int[] dp = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            dp[i] = dp[i - 1] + visitors[i];
        }
        
        int maxVisitors = 0;  // 최대 방문자 수
        int maxPeriods = 0;  // 최대 방문자 수가 나오는 기간의 개수
        
        // X일 동안의 기간을 순회하며 최대 방문자 수와 해당 기간의 개수 찾기
        for (int i = X; i <= N; i++) {
            // X일 동안의 방문자 수 계산
            int totalVisitors = dp[i] - dp[i - X];
            
            // 최대 방문자 수 및 해당 기간의 개수 업데이트
            if (totalVisitors > maxVisitors) {
                maxVisitors = totalVisitors;
                maxPeriods = 1;
            } else if (totalVisitors == maxVisitors) {
                maxPeriods++;
            }
        }
        
        // 결과 배열 반환
        return new int[]{maxVisitors, maxPeriods};
    }
    
}