| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 1252 | 340 | 231 | 30.275% |
문제
화영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1≤N≤100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 화영이는 가급적 많은 이득을 얻을 수 있도록 보석을 가져가려 한다. 이때, 다음 세 가지의 조건이 만족되어야 한다.
- 보석들은 1번 보석부터 N번 보석까지가 차례대로 놓여 있고, 화영이는 1번 보석이 놓여 있는 곳부터 N번 보석이 놓여 있는 곳까지 순서대로 이동한다. 그런데 보석들 사이사이에는 함정이 설치되어 있어서 보석을 줍다가 도중에 뒤로 돌아갈 수는 없다. 따라서 화영이는 보석이 놓여 있는 위치에서 보석을 줍거나 혹은 그냥 지나치고 다음 보석이 있는 위치로 이동하게 된다.
- 유적에는 함정뿐 아니라 경보 장치도 설치되어 있다. 이 장치는 유적에 들어온 사람이 보석을 주우면 침입자로 간주하고, 침입자가 보석 줍기를 멈추는 순간 유적을 무너뜨리도록 설계되어 있다. 단, 이 경보 장치는 수를 잘 세지 못하기 때문에 M(1≤M≤N)개 이상의 보석을 연속으로 주우면 헷갈려서 유적을 조금 늦게 무너뜨린다. 따라서 보석을 줍기 시작하면 그 위치에 있는 보석을 포함하여 M개 이상의 보석을 연속적으로 주워야 하고, 보석 줍기를 한 번 멈춘 후에는 다른 보석을 주울 틈도 없이 서둘러서 유적을 빠져나와야 한다.
- 보석들은 무겁기 때문에, 기왕에 보석을 주워 가는 것이라면 가급적 비싼 보석들로 주워가려 한다. 즉, 주운 보석들의 가치의 총 합을 최대로 하려 한다. 단, 일부 보석들의 가치는 음수일 수도 있다.
보석들의 개수가 매우 많기 때문에, 화영이는 이 문제를 컴퓨터를 이용하여 풀기로 하였다. 보석들에 대한 정보가 주어졌을 때, 위의 조건들을 만족하면서 이동할 때 얻을 수 있는 가치의 총 합의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 차례로 각 보석의 가치가 주어진다. 각 보석의 가치의 절댓값은 2,000이하의 정수이다.
출력
첫째 줄에 가치의 총 합의 최댓값을 출력한다.
접근
최소 M개 이상의 연속적인 최대합을 찾는 문제이다.
우선 각 인덱스마다 M개의 연속합을 구해놓는다.
그리고 순회하면서 i - 1번째 테이블 + arr[i]와 sum[i]의 값중 큰 값을 취하면 된다.
답은 dp tabel의 최댓값이다.
풀이
sum 배열에서 M개의 연속합을 구했다.
그리고, dp 배열에서 위 점화식을 이용한다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
int N, M, ans = 0, arr[100001], dp[100001], sum[100001];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
CIN2(N, M);
FUP(i, 1, N)
{
CIN(arr[i]);
sum[i] = sum[i - 1] + arr[i];
if (i > M) sum[i] -= arr[i - M];
}
dp[M] = sum[M];
ans = max(ans, dp[M]);
FUP(i, M + 1, N)
{
dp[i] = max(dp[i - 1] + arr[i], sum[i]);
ans = max(dp[i], ans);
}
COUT(ans);
return 0;
}
Beginner
0개의 댓글
