[Algorithm] C++/Python 백준 15678번 : 연세워터파크
연세대학교에서는 매년 여름 깜짝 워터파크를 개장한다. 워터파크 개장을 막는 것이 힘들다고 판단한 학교에서는 학생들이 워터파크를 더 즐길 수 있도록 정수 \(K_i\)가 쓰여진 징검다리 \(N\)개를 놓아 두었다. 학생들은 이 징검다리를 이용해 게임을 진행하며, 게임의 목표는 징검다리에 쓰인 정수의 합을 최대화하는 것이다.
게임의 규칙은 다음과 같다:
- 각 사람은 시작점으로 사용할 징검다리 하나를 아무 것이나 하나 고른다.
- 시작점에서 출발한 뒤 계속 점프하여 징검다리를 몇 개든 마음대로 밟은 뒤, 나오고 싶을 때 나온다. 시작점에서 바로 나오는 것도 가능하다.
- 징검다리 간 점프는 인덱스 차이가 \(D\) 이하이어야 한다.
- 어떤 징검다리도 두 번 이상 밟을 수 없다.
이러한 규칙 하에서, 학생들이 얻을 수 있는 최대 점수를 구하는 문제이다. 점수는 시작점에서부터 밟은 모든 징검다리에 쓰여진 정수의 합으로 계산된다. 징검다리의 수 \(N\)과 각 징검다리에 쓰인 정수 \(K_i\)가 주어질 때, 가능한 최대 점수를 구하는 프로그램을 작성해야 한다.
문제 : https://www.acmicpc.net/problem/15678
 |
|---|
접근 방식
이 문제는 동적 계획법(Dynamic Programming)을 이용하여 효율적으로 해결할 수 있다. 각 징검다리를 시작점으로 삼았을 때, 그 지점까지 올 수 있는 최대 점수를 계산하고, 이를 기반으로 전체적으로 가능한 최대 점수를 찾는 방식이다. 문제의 주요 제약 조건은 징검다리 간 점프 시 인덱스 차이가 \(D\) 이하이어야 하며, 한 번 밟은 징검다리를 다시 밟을 수 없다는 점이다.
이를 위해, 각 징검다리 \(i\)까지 올 수 있는 최대 점수를 저장하는 DP 배열 \(DP[i]\)를 정의한다. \(DP[i]\)는 징검다리 \(i\)를 밟을 때까지의 최대 점수를 의미한다. \(DP[i]\)를 계산하기 위해서는 \(i-D\)부터 \(i-1\)까지의 징검다리 중에서 최대 점수를 가진 징검다리를 선택하여 \(K[i]\)를 더하는 방식으로 접근할 수 있다.
하지만, \(N\)이 최대 \(10^5\)이기 때문에 단순한 반복문으로는 시간 초과가 발생할 수 있다. 이를 해결하기 위해 Deque를 활용하여 슬라이딩 윈도우 내에서 최대 값을 효율적으로 관리한다. Deque의 front에는 현재 윈도우 내에서 최대 \(DP[j]\) 값을 가진 인덱스를 유지하며, 이를 통해 \(DP[i]\)를 빠르게 계산할 수 있다.
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
52
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int N, D;
cin >> N >> D;
vector<ll> K(N+1);
for(int i=1;i<=N;i++) cin >> K[i];
// Initialize DP array
vector<ll> DP(N+1, 0);
// Initialize deque to store indices, front has the max DP[j]
deque<int> dq;
ll max_ans = LLONG_MIN;
for(int i=1;i<=N;i++){
// Remove indices out of the window [i-D, i-1]
while(!dq.empty() && dq.front() < i - D){
dq.pop_front();
}
// Calculate DP[i]
if(!dq.empty()){
ll best = DP[dq.front()];
if(best > 0){
DP[i] = K[i] + best;
}
else{
DP[i] = K[i];
}
}
else{
DP[i] = K[i];
}
// Update the deque: remove from back while DP[j] <= DP[i]
while(!dq.empty() && DP[dq.back()] <= DP[i]){
dq.pop_back();
}
dq.push_back(i);
// Update the maximum answer
max_ans = max(max_ans, DP[i]);
}
cout << max_ans;
}
코드 설명
- 입력 처리: 첫 줄에서 \(N\)과 \(D\)를 입력받고, 다음 \(N\)개의 줄에서 각 징검다리에 쓰인 정수 \(K_i\)를 입력받는다.
- DP 배열 초기화: \(DP[i]\)는 징검다리 \(i\)를 밟을 때까지의 최대 점수를 저장한다. 초기에는 모두 0으로 설정한다.
- Deque 초기화: Deque를 사용하여 현재 윈도우 내에서 최대 \(DP[j]\) 값을 가진 인덱스를 관리한다. Deque의 front는 항상 현재 윈도우에서 가장 큰 \(DP[j]\) 값을 가진 인덱스를 유지한다.
- DP 계산: 각 징검다리 \(i\)에 대해, \(i-D\)부터 \(i-1\)까지의 징검다리 중 최대 \(DP[j]\) 값을 찾고, 이를 \(K[i]\)와 더하여 \(DP[i]\)를 계산한다. 만약 이전까지의 최대 값이 음수라면, 현재 징검다리 \(i\)만을 선택한다.
- Deque 업데이트: 현재 \(DP[i]\)가 Deque의 뒤에 있는 값들보다 크거나 같으면, Deque의 뒤에서부터 제거하여 Deque가 항상 내림차순을 유지하도록 한다. 그런 다음 현재 인덱스 \(i\)를 Deque에 추가한다.
- 최대 점수 업데이트: 각 단계에서 \(DP[i]\)를 전체 최대 점수 \(max\_ans\)와 비교하여 업데이트한다.
- 결과 출력: 최종적으로 \(max\_ans\)를 출력한다.
C++ without library 코드와 설명
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
using namespace std;
typedef long long ll;
struct Deque {
int data[100005];
int front;
int back;
Deque() : front(0), back(-1) {}
bool empty() {
return front > back;
}
void push_back(int x){
back++;
data[back] = x;
}
void pop_front(){
front++;
}
void pop_back(){
back--;
}
int get_front(){
return data[front];
}
int get_back(){
return data[back];
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int N, D;
cin >> N >> D;
ll K_arr[100005];
for(int i=1;i<=N;i++) cin >> K_arr[i];
// Initialize DP array
ll DP_arr[100005];
for(int i=0;i<=N;i++) DP_arr[i] = 0;
// Initialize custom deque
Deque dq;
ll max_ans = -9223372036854775807LL;
for(int i=1;i<=N;i++){
// Remove indices out of the window [i-D, i-1]
while(!dq.empty() && dq.get_front() < i - D){
dq.pop_front();
}
// Calculate DP[i]
if(!dq.empty()){
ll best = DP_arr[dq.get_front()];
if(best > 0){
DP_arr[i] = K_arr[i] + best;
}
else{
DP_arr[i] = K_arr[i];
}
}
else{
DP_arr[i] = K_arr[i];
}
// Update the deque: remove from back while DP[j] <= DP[i]
while(!dq.empty() && DP_arr[dq.get_back()] <= DP_arr[i]){
dq.pop_back();
}
dq.push_back(i);
// Update the maximum answer
if(DP_arr[i] > max_ans){
max_ans = DP_arr[i];
}
}
cout << max_ans;
}
코드 설명
이 코드는 표준 라이브러리의 vector, deque, climits 등을 사용하지 않고, 필요한 기능을 직접 구현하여 작성되었다. 기본적인 로직은 이전 C++ 코드와 동일하며, Deque의 기능을 구조체로 직접 구현하였다.
- 입력 처리: \(N\), \(D\), 그리고 각 징검다리에 쓰인 정수 \(K_i\)를 입력받는다. 징검다리의 정수는
K_arr배열에 저장된다. - DP 배열 초기화:
DP_arr배열을 사용하여 각 징검다리 \(i\)를 밟을 때까지의 최대 점수를 저장한다. 초기에는 모두 0으로 설정한다. - Custom Deque 구조체:
Deque구조체를 정의하여, 표준 라이브러리의deque를 대체한다. 배열과 포인터(front,back)를 사용하여 Deque의 기본적인 기능을 구현하였다.push_back(int x): Deque의 뒤에 요소를 추가한다.pop_front(): Deque의 앞에서 요소를 제거한다.pop_back(): Deque의 뒤에서 요소를 제거한다.get_front(): Deque의 앞 요소를 반환한다.get_back(): Deque의 뒤 요소를 반환한다.empty(): Deque가 비어있는지 확인한다.
- DP 계산: 각 징검다리 \(i\)에 대해, \(i-D\)부터 \(i-1\)까지의 징검다리 중 최대 \(DP[j]\) 값을 찾고, 이를 \(K[i]\)와 더하여 \(DP[i]\)를 계산한다. 만약 이전까지의 최대 값이 음수라면, 현재 징검다리 \(i\)만을 선택한다.
- Deque 업데이트: 현재 \(DP[i]\)가 Deque의 뒤에 있는 값들보다 크거나 같으면, Deque의 뒤에서부터 제거하여 Deque가 항상 내림차순을 유지하도록 한다. 그런 다음 현재 인덱스 \(i\)를 Deque에 추가한다.
- 최대 점수 업데이트: 각 단계에서 \(DP[i]\)를 전체 최대 점수 \(max\_ans\)와 비교하여 업데이트한다.
- 결과 출력: 최종적으로 \(max\_ans\)를 출력한다.
Python 코드와 설명
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
import sys
from collections import deque
def main():
input = sys.stdin.readline
N, D = map(int, input().split())
K = [0] + list(map(int, input().split()))
DP = [0] * (N + 1)
dq = deque()
max_ans = -10**18
for i in range(1, N + 1):
# Remove indices out of the window [i-D, i-1]
while dq and dq[0] < i - D:
dq.popleft()
# Calculate DP[i]
if dq:
best = DP[dq[0]]
if best > 0:
DP[i] = K[i] + best
else:
DP[i] = K[i]
else:
DP[i] = K[i]
# Update the deque: remove from back while DP[j] <= DP[i]
while dq and DP[dq[-1]] <= DP[i]:
dq.pop()
dq.append(i)
# Update the maximum answer
if DP[i] > max_ans:
max_ans = DP[i]
print(max_ans)
if __name__ == "__main__":
main()
코드 설명
Python에서는 deque를 사용하여 슬라이딩 윈도우 내에서 최대 DP[j]DP[j] 값을 효율적으로 관리한다.
- 입력 처리: sys.stdin.readline을 사용하여 빠르게 입력을 받는다. NN, DD, 그리고 각 징검다리에 쓰인 정수 KiKi를 입력받는다.
- DP 배열 및 Deque 초기화: DP[i]DP[i]를 저장할 리스트와 Deque를 초기화한다.
- DP 계산 및 Deque 업데이트: 각 징검다리 ii에 대해 DP[i]DP[i]를 계산하고, Deque를 업데이트한다.
- 최대 점수 업데이트: 각 단계에서 최대 점수를 지속적으로 갱신한다.
- 결과 출력: 최종적으로 최대 점수를 출력한다.
결론
이번 문제는 동적 계획법과 효율적인 자료 구조인 Deque를 활용하여 시간 복잡도를 \(O(N)\)으로 줄일 수 있었다. 슬라이딩 윈도우 내에서 최대 값을 효율적으로 관리하는 방법을 이해하는 데 도움이 되는 문제였다. 특히, 큰 입력 크기에서도 빠르게 동작하도록 최적화된 코드를 작성하는 것이 중요했으며, Deque를 활용한 최적화 기법이 매우 유용함을 다시 한번 확인할 수 있었다. 앞으로 유사한 문제를 만났을 때, 이번에 배운 접근 방식을 응용하여 효율적으로 문제를 해결할 수 있을 것이다.
Comments