[BOJ][C++] 백준 10025번: 게으른 백곰 (Silver III)

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

10025번: 게으른 백곰

 

문제

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

우리 안은 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만큼 떨어진 거리 내에 있는 얼음들의 합(최댓값)을 출력한다.

 

풀이

// 풀이 : https://whkakrkr.tistory.com

#include <bits/stdc++.h>

using namespace std;

const int INF = 4000001;

int main() {
    ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	// input
	int n,k, g,x;
	cin >> n >> k;
	vector<int>v(INF, 0);
	for(int i=0; i<n; i++) {
	    cin >> g >> x;
	    v[x] = g;
	}
	
	// solution
	long long cur=0, ans=0;
	int left=0, right=0;
	for(; right<=2*k; right++) {
	    cur += v[right];
	}

	while(right<INF) {
	    ans = max(cur, ans);
	    cur -= v[left];
	    cur += v[right];
	    left++;
	    right++;
	}
	
	cout << ans;

    return 0;
}

2025.04.22

 

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>

using namespace std;

const int SIZE = 1000000;

int maxIce(int k, int end_point, vector<int>&position) {
    int section = 2*k + 1;
    int section_ice = 0;
    for(int i=0; i<section; i++){
        if(i > end_point)
            break;
        
        section_ice += position[i];
    }
    
    int ans = section_ice;
    for(int i=section; i<=end_point; i++) {
        section_ice -= position[i-section];
        section_ice += position[i];
        ans = max(ans, section_ice);
    }
    
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int n, k;
    cin >> n >> k;
    vector<int> position(SIZE+1, 0);
    int g, x, end_point=0;
    while(n--) {
        cin >> g >> x;
        position[x] = g;
        end_point = max(end_point, x);
    }
    
    cout << maxIce(k, end_point, position);
    
    return 0;
}

/*
 */

2021.08.08 ?