C# 백준 10025 게으른 백곰

게으른 백곰 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

7131

2158

1512

29.155%

문제

더운 여름날 동물원의 백곰 앨버트는 너무 더워서 꼼짝도 하기 싫다. 다행히도 사육사들이 앨버트의 더위를 식히기 위해 얼음이 담긴 양동이들을 가져다 주었다. 앨버트가 가장 적은 거리만 움직이고도 최대한 많은 얼음으로 더위를 식힐 수 있도록 도와주자.

우리 안은 1차원 배열로 생각하며, 총 N(1 ≤ N ≤ 100000)개의 얼음 양동이들이 xi(0 ≤ xi ≤ 1,000,000)좌표마다 놓여 있고 각 양동이 안에는 gi(1 ≤ gi ≤ 10,000)씩의 얼음이 들어 있다. 일단 앨버트가 자리를 잡으면 그로부터 좌우로 K(1 ≤ K ≤ 2,000,000) 만큼 떨어진 양동이까지 닿을 수 있다. 앨버트는 양동이가 놓여 있는 자리에도 자리잡을 수 있다. 모든 얼음 양동이의 위치는 다르다.

앨버트가 최적의 자리를 골랐을 때 얼음의 합을 구하시오. 즉, 얼음들의 합의 최댓값을 구해야 한다.

입력

첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다.

출력

앨버트가 택한 최적 위치로부터 K만큼 떨어진 거리 내에 있는 얼음들의 합(최댓값)을 출력한다.

 

예제 입력 1

4 3
4 7
10 15
2 2
5 1

예제 출력 1

11

힌트

앨버트가 x=4에 자리를 잡으면 x=1, x=2, x=7에 있는 얼음 양동이에 닿을 수 있다.

 

내가 푼 코드

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Prob10025_게으른_백곰
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] cage = new int[1000001];
            int cageMax = int.MinValue;
            long max = int.MinValue;
            long currentMax = 0;

            string[] arr = Console.ReadLine().Split();

            int n = int.Parse(arr[0]);
            int k = int.Parse(arr[1]) * 2;

            for (int i = 0; i < n; i++)
            {
                arr = Console.ReadLine().Split();

                int a = int.Parse(arr[0]);
                int b = int.Parse(arr[1]);

                cage[b] = a;

                if(cageMax < b)
                {
                    cageMax = b;
                }
            }
       
            if (k > cageMax)
            {               
                for (int i = 0; i < cageMax + 1; i++)
                {              
                    currentMax += cage[i];                
                }
                Console.WriteLine(currentMax);
                return;
            }
            else
            {
                for (int i = 0; i < k + 1; i++)
                {
                    currentMax += cage[i];
                }

                max = currentMax > max ? currentMax : max;

                for (int i = 0; i < cage.Length; i++)
                {
                    k++;
                    currentMax = currentMax + (cage[k] - cage[i]);
                    
                    max = Math.Max(max, currentMax);

                    if (k >= cageMax)
                    {
                        Console.WriteLine(max);
                        return;
                    }        
                }
            }

        }
    }
}