문제 링크
1. 문제 풀이
얼음 양동이들의 좌표와 얼음의 양이 주어져 있고 백곰이 좌우로 $K$ 만큼 떨어진 양동이에 닿을 수 있을 때 최적의 자리에서 얼음의 합의 최댓값을 구해야 하는 문제다. 누적합, 슬라이딩 윈도우, 투 포인터 3가지 방식으로 모두 풀이가 가능하다. 백곰은 양동이가 있는 좌표에도 있을 수 있으며 좌우로 $K$ 만큼 떨어진 양동이도 잡을 수 있으므로 잡을 수 있는 범위의 크기는 $2 \times K + 1$ 이다.
2. 코드
1. 누적합 [Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[][] input = new int[N][2]; // 양동이의 얼음의 양과 좌표를 임시 저장
int maxLen = 0; // 양동이의 좌표의 최댓값
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
input[i][0] = Integer.parseInt(st.nextToken());
input[i][1] = Integer.parseInt(st.nextToken());
maxLen = Math.max(maxLen, input[i][1]);
}
// 인덱스에 양동이의 좌표, 값에 양동이의 얼음의 양 저장
int[] arr = new int[1 + maxLen];
for (int i = 0; i < N; i++) {
arr[input[i][1]] = input[i][0];
}
// 누적합 배열 계산
int[] pSum = new int[1 + maxLen];
pSum[0] = arr[0];
for (int i = 1; i <= maxLen; i++) {
pSum[i] = pSum[i - 1] + arr[i];
}
// 닿을 수 있는 범위
int size = 2 * K + 1;
// 모든 양동이에 닿을 수 있으면 모든 양동이의 얼음의 양의 합을 출력하고 리턴
if (size > maxLen) {
System.out.println(pSum[maxLen]);
return;
}
// 누적합 배열에서 구간을 이동하며 최댓값 계산
int max = 0;
for (int i = 0; i <= maxLen - size; i++) {
max = Math.max(max, pSum[i + size] - pSum[i]);
}
System.out.println(max);
}
}
|
2. 슬라이딩 윈도우 [Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[][] input = new int[N][2]; // 양동이의 얼음의 양과 좌표를 임시 저장
int maxLen = 0; // 양동이의 좌표의 최댓값
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
input[i][0] = Integer.parseInt(st.nextToken());
input[i][1] = Integer.parseInt(st.nextToken());
maxLen = Math.max(maxLen, input[i][1]);
}
// 인덱스에 양동이의 좌표, 값에 양동이의 얼음의 양 저장
int[] arr = new int[1 + maxLen];
for (int i = 0; i < N; i++) {
arr[input[i][1]] = input[i][0];
}
// 윈도우의 크기
int windowSize = 2 * K + 1;
// 윈도우가 좌표의 최댓값보다 크면 모든 양동이에 닿을 수 있으므로 모든 양동이의 얼음의 합을 출력하고 리턴
if (windowSize > maxLen) {
int sum = 0;
for (int n : arr) {
sum += n;
}
System.out.println(sum);
return;
}
// 초기 윈도우 내 얼음의 합 계산
int sum = 0;
for (int i = 0; i < windowSize; i++) {
sum += arr[i];
}
// 윈도우를 이동하며 얼음의 합의 최댓값 계산
int max = sum;
for (int i = 0; i <= maxLen - windowSize; i++) {
sum = sum - arr[i] + arr[i + windowSize];
max = Math.max(max, sum);
}
System.out.println(max);
}
}
|
3. 투 포인터 [Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[][] input = new int[N][2]; // 양동이의 얼음의 양과 좌표를 임시 저장
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
input[i][0] = Integer.parseInt(st.nextToken());
input[i][1] = Integer.parseInt(st.nextToken());
}
// 양동이의 좌표를 기준으로 정렬
Arrays.sort(input, ((o1, o2) -> Integer.compare(o1[1], o2[1])));
int left = 0;
int right = 0;
int sum = 0;
int max = 0;
while (right < N) {
// 더 잡을 수 있으면 오른쪽 포인터를 이동하며 더 잡을 수 없으면 왼쪽 포인터를 이동
if (input[right][1] - input[left][1] > (2 * K + 1)) {
sum -= input[left++][0];
} else {
sum += input[right++][0];
max = Math.max(max, sum);
}
}
System.out.println(max);
}
}
|
4. 누적합 [C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<pair<int, int>> input(n); // 양동이의 얼음의 양과 좌표를 임시 저장
int maxLen = 0; // 양동이의 좌표의 최댓값
for (auto& p : input) {
cin >> p.first >> p.second;
maxLen = max(maxLen, p.second);
}
// 인덱스에 양동이의 좌표, 값에 양동이의 얼음의 양 저장
vector<int> v(1 + maxLen);
for (auto p : input) {
v[p.second] = p.first;
}
// 누적합 배열 계산
vector<int> psum(1 + maxLen);
psum[0] = v[0];
for (int i = 1; i <= maxLen; i++) {
psum[i] = psum[i - 1] + v[i];
}
// 닿을 수 있는 범위
int sz = 2 * k + 1;
// 모든 양동이에 닿을 수 있으면 모든 양동이의 얼음의 양의 합을 출력하고 리턴
if (sz > maxLen) {
cout << psum[maxLen];
return 0;
}
// 누적합 배열에서 구간을 이동하며 최댓값 계산
int mx = 0;
for (int i = 0; i <= maxLen - sz; i++) {
mx = max(mx, psum[i + sz] - psum[i]);
}
cout << mx;
}
|
5. 슬라이딩 윈도우 [C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<pair<int, int>> input(n); // 양동이의 얼음의 양과 좌표를 임시 저장
int maxLen = 0; // 양동이의 좌표의 최댓값
for (auto& p : input) {
cin >> p.first >> p.second;
maxLen = max(maxLen, p.second);
}
// 인덱스에 양동이의 좌표, 값에 양동이의 얼음의 양 저장
vector<int> v(1 + maxLen);
for (auto p : input) {
v[p.second] = p.first;
}
// 윈도우의 크기
int sz = 2 * k + 1;
// 윈도우가 좌표의 최댓값보다 크면 모든 양동이에 닿을 수 있으므로 모든 양동이의 얼음의 합을 출력하고 리턴
if (sz > maxLen) {
int sum = 0;
for (int x : v) {
sum += x;
}
cout << sum;
return 0;
}
// 초기 윈도우 내 얼음의 합 계산
int sum = 0;
for (int i = 0; i < sz; i++) {
sum += v[i];
}
// 윈도우를 이동하며 얼음의 합의 최댓값 계산
int mx = sum;
for (int i = 0; i <= maxLen - sz; i++) {
sum = sum - v[i] + v[i + sz];
mx = max(mx, sum);
}
cout << mx;
}
|
6. 투 포인터 [C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<pair<int, int>> input(n); // 양동이의 얼음의 양과 좌표를 임시 저장
for (auto& p : input) cin >> p.second >> p.first;
sort(input.begin(), input.end()); // 양동이의 좌표를 기준으로 정렬
int l = 0;
int r = 0;
int sum = 0;
int mx = 0;
while (r < n) {
// 더 잡을 수 있으면 오른쪽 포인터를 이동하며 더 잡을 수 없으면 왼쪽 포인터를 이동
if (input[r].first - input[l].first > (2 * k + 1)) {
sum -= input[l++].second;
} else {
sum += input[r++].second;
mx = max(mx, sum);
}
}
cout << mx;
}
|
3. 풀이 정보
1. 누적합 [Java]
| 언어 | 시간 | 메모리 | 코드 길이 |
|---|
| Java 11 | 332 ms | 48012 KB | 1772 B |
2. 슬라이딩 윈도우 [Java]
| 언어 | 시간 | 메모리 | 코드 길이 |
|---|
| Java 11 | 344 ms | 44148 KB | 1906 B |
3. 투 포인터 [Java]
| 언어 | 시간 | 메모리 | 코드 길이 |
|---|
| Java 11 | 468 ms | 45028 KB | 1339 B |
4. 누적합 [C++]
| 언어 | 시간 | 메모리 | 코드 길이 |
|---|
| C++ 17 | 24 ms | 10620 KB | 1227 B |
5. 슬라이딩 윈도우 [C++]
| 언어 | 시간 | 메모리 | 코드 길이 |
|---|
| C++ 17 | 20 ms | 6712 KB | 1311 B |
6. 투 포인터 [C++]
| 언어 | 시간 | 메모리 | 코드 길이 |
|---|
| C++ 17 | 24 ms | 2804 KB | 812 B |