[백준] 10025번 : 게으른 백곰
문제 푼 날짜 : 2021-10-06
문제
문제 링크 : https://www.acmicpc.net/problem/10025
접근 및 풀이
슬라이딩 윈도우 알고리즘을 이용하는 문제였다.
코드는 아래의 생각대로 구현하였다.
- 문제에 주어진 최대 크기의 배열을 선언하고, 얼음이 있는 위치에 입력값을 넣어준다.
- 백곰 앨버트는 자리잡은 곳에서 좌우로 K씩 먹는다고 하였으니, 최초 2*K 만큼 커버할 수 있다.
- 처음부터 배열의 값들을 더해주다가, 2*K + 1 부터 인덱스가 가장 낮은 위치의 값을 빼주고 다음 위치의 값을을 추가해준다. 이 때, 더한 값의 최댓값을 업데이트해준다.
코드
// 백준 10025번 : 게으른 백곰
#include <iostream>
using namespace std;
int N, K, ans;
int arr[1000001];
int main() {
cin >> N >> K;
for (int i = 0; i < N; i++) {
int g, x;
cin >> g >> x;
arr[x] = g;
}
K = 2 * K + 1;
int sum = 0;
for (int i = 0; i <= 1000001; i++) {
if (i >= K) {
sum -= arr[i - K];
}
sum += arr[i];
ans = max(ans, sum);
}
cout << ans;
return 0;
}
결과
// 백준 10025번 : 게으른 백곰
#include <iostream>
using namespace std;
int N, K, ans;
int arr[1000001];
int main() {
cin >> N >> K;
for (int i = 0; i < N; i++) {
int g, x;
cin >> g >> x;
arr[x] = g;
}
K = 2 * K + 1;
int sum = 0;
for (int i = 0; i <= 1000001; i++) {
if (i >= K) {
sum -= arr[i - K];
}
sum += arr[i];
ans = max(ans, sum);
}
cout << ans;
return 0;
}
피드백
언제나 입력값에 대한 범위체크는 꼼꼼히하고 구현하도록 하자.
Author And Source
이 문제에 관하여([백준] 10025번 : 게으른 백곰), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bestcoders/백준-10025번-게으른-백곰저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)