[BOJ] 21921 블로그

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

21921번: 블로그

 

유형

누적합

슬라이딩 윈도우 

 

 

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace _21921
{
    class Program
    {
        static void Main()
        {
            // 5 2
            // 1 4 2 5 1
            
            // 블로그를 시작 하고 지난 일수 N
            // X일 동안 가자 많이 들어온 방문자 수
            
            // [1 4] 2 5 1      5      
            // 1 [4 2] 5 1      6
            // 1 4 [2 5] 1      7
            // 1 4 2 [5 1]      6
            
            // 첫줄 최대 방문자 수 : 7 
            // 둘째 줄 기간이 몇개 : 1
            
            
            // 7 5
            // [1 1 1 1 1] 5 1      5   
            // 1 [1 1 1 1 5] 1      9
            // 1 1 [1 1 1 5 1]      9
            
            // 첫줄 최대 방문자 수 : 9 
            // 둘째 줄 기간이 몇개 : 2

            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
            int[] nx = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse);

            int n = nx[0];  
            int x = nx[1];
            int[] arr = new int[1].Concat(
                Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse)
            ).ToArray();

            int sum = 0;
            int max = 0;
            int cnt = 0;
            
            for (int i = 1; i <= n - x + 1; i++)
            {
                if (i == 1) //처음에만 구간합 구하기 
                {
                    for (int j = 1; j <= x; j++)    
                    {
                        sum += arr[j];
                    }

                    max = sum;  //최초 max 설정 (등장)
                    cnt = 1;    //최초 max count 설정 

                }
                else
                {
                    //슬라이딩 윈도우
                    int A = arr[i - 1];
                    int B = arr[i + x - 1];
                    int sum2 = sum - A + B;

                    //새로운 구간합이 현재 까지 최대 구간합 보다 클경우 
                    if (sum2 > max)
                    {
                        //최대 등장 횟수 초기화 
                        cnt = 1;
                        //max 갱신
                        max = sum2;
                    }
                    else if (sum2 == max)
                    {
                        //같다면 max 등장 횟수 증가 
                        cnt++;
                    }
                    
                    sum = sum2; //변경된 구간합으로 갱신 
                    
                }
            }
            
            if (max == 0)
                sw.Write("SAD");
            else
                sw.Write("{0}\n{1}", max, cnt);

            sr.Close();
            sw.Close();

        }
    }
    
}

 

 

 

힌트

https://ji-musclecode.tistory.com/37

https://jinho9610.tistory.com/38