문제 URL : https://www.acmicpc.net/problem/2616
2616번: 소형기관차
첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있
www.acmicpc.net
문제접근법 :
소형 기관차가 최대로 끌수 있는 객차의 수가 주어질 때, 소형 기관차 3대를 이용하여 최대로 운송할 수 있는 손님 수를 구하는 문제입니다.
배열의 [1,n]까지의 누적합 배열을 sum[n]이라 할때
소형기간차가 최대로 끌수있는 객차수가 k일때
객차수가 n대일때
소형차 x대를 이용해서 운송할수있는 손님수의 최대값의 배열을 dp[x][n]이라할때
소형차 1대를 이용해서 운송할수있는 손님수의 최대값의 점화식을 구한다면
dp[x][i]=sum[i]-sum[i-k] 입니다.
그렇지만 2대를 이용해서 운송할수있는 최대값의 점화식을 구한다면
1대에서 구했던것을 하나더 추가해서 max(dp[2][j-1],max[1][i-k]+sum[i]-sum[i-k])가 됩니다.
이런식으로 2대를 구했다면 마찬가지로 3대에서도 똑같은 점화식이 성립니다.
즉 여러대여도 상관이없다는 뜻이죠
점화식은
이분의 블로그를 참고했습니다. :https://comyoung.tistory.com/184
[백준] 2616번 소형기관차
2616 소형기관차 문제 기차는 맨 앞에 있는 기관차 1대가 손님이 탄 객차 여러 칸을 끌고 간다. 기관차가 고장나면 기차를 운행할 수 없게 되므로 최근 철도청은 기관차 고장에 대비하여 몇몇 역
comyoung.tistory.com
소스코드 :
|
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
|
//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
int n, k;
vector<int> v, sum;
int res[4][50001];
void input() {
cin >> n;
v.resize(n + 1);
sum.resize(n + 1);
for (int i = 1; i <= n; i++) {
cin >> v[i];
sum[i] += v[i] + sum[i - 1];
}
cin >> k;
}
void solve() {
for (int i = 1; i <= 3; i++) {
for (int j = i * k; j <= n; j++) {
res[i][j] = max(res[i][j - 1],res[i-1][j-k]+(sum[j]-sum[j-k]));
}
}
cout << res[3][n] << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 또는 논리적인오류등 어쩍지적이든 어떤질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 1485 정사각형 (2) | 2021.07.02 |
|---|---|
| 백준 1331 나이트 투어 (0) | 2021.07.02 |
| 백준 18352 특정 거리의 도시 찾기 (0) | 2021.06.28 |
| 백준 12767 Ceiling Function (0) | 2021.06.25 |
| 백준 9935 문자열 폭발 (0) | 2021.06.24 |
