https://www.acmicpc.net/problem/6988
6988번: 타일 밟기
첫째 줄에는 타일의 개수 N이 주어진다. N은 3 이상 3,000 이하이다. 둘째 줄에는 N개의 타일에 적힌 자연수들이 증가하는 순서로 빈칸을 사이에 두고 주어진다. 타일에 적힌 자연수들은 각각 1,000,000 이하이다.
www.acmicpc.net
백준 6988번 문제이자, 정보올림피아드 초등부 2008년도 전국본선 3번문제 타일 밟기 문제이다.
문제 분석
타일이 최대 3000개가 주어지고, 타일 번호는 정렬되어 있다.
최소 3개 이상 연속된 타일의 숫자 합 중 최대값을 구해야 하고, 연속된 타일이라 함은
타일들 간에 값의 차이가 일정해야 한다는 것이다.
등차수열을 이루는 타일 값들의 합이 최대여야 한다는 것
타일에 적힌 수는 100만까지 나올 수 있다.
알고리즘 설계 및 시간복잡도 분석
타일에 적힌 수는 자연수이므로 1부터 100만의 범위이다.
그러면 타일 간 값의 차이는 1부터 50만 정도가 된다고 볼 수 있다 대충
1 50만 100만1 이렇게 하면 3개가 된다.
즉 1 500000 1000001 이렇게 인데, 사실 100만1은 안나오지만, 대충 타일 값 차이가 50만 가까이가
최대값이라고 보면 된다.
따라서 타일간 차이값인 diff값을 모두 다 찾아보면서 순회하려면 diff값이 50만개가 될 것이고
diff값 별 타일 모두를 다 훑어야 하므로 for-loop 도는 횟수는 50만 * 3천 정도 인데
이 값은 15억 정도 되므로, 15초 이상 걸리는 알고리즘 이라고 볼 수있다. 고로 Time Limit Exceed가
자명한 알고리즘이라는 뜻
그러면 이 계산량을 줄여야 하는데, N값이 3000이므로 꽤나 작다.
3000이라면 //(O(N^2)//)알고리즘을 짜도 돌아간다는 뜻.
여기서 잘 모르겠어서 아래의 알고리즘 분류를 "보기"를 눌러서 확인해 보았는데
다이나믹 프로그래밍이라고 힌트를 얻었다.
그러면 N값을 기준으로 메모이제이션 배열을 활용하면 될 것 같은데, N크기에 맞는 2차원 디피까지는 가능할 것 같다.
그렇다면 dp 배열 인덱스에 diff값을 넣을 수는 없다. 메모리 문제도 있고 시간 문제도 있고
그래서 //(dp[3000][3000]//)식으로 잡고, //(dp[i][j]//)라 했을 때, //(i//)가 마지막 인덱스고 //(j//)가 직전 인덱스로 해서
//(arr[i] - arr[j]//)로 diff값을 구할 수 있으니, 이를 활용해 보기로 했다.
dp[i][j] = i번째에서 끝나고, 그 직전에 arr[j]의 값을 갖는 시퀀스 합의 최대값
이라고 정의해보자.
처음 3개짜리만 대상으로 dp배열을 모두 전처리 해 놓은 뒤,
모든 dp배열을 돌면서, arr[j], arr[i]를 통해서 다음에 나올 수 있는 값을 구해서, 그 값이 존재하는 지
확인한 뒤, 존재한다면 그 인덱스를 //(k//)라 하고, //(dp[k][i]//)에 //(dp[i][j] + arr[k]//)를 넣는 식으로 구하면 될 듯하다.
값이 존재하는지는, 값의 범위가 1부터 100만이므로 배열을 잡기 보다는 c++ stl map같은 자료구조를 쓰면 좋을 것 같다.
배열로 잡는다면 값 자체는 3000개라서 sparse한 배열이 될 것이고, 메모리가 터질 수 있으므로
구현 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
int arr[3005];
map<int, int> mm;
ll dp[3005][3005]; // dp[i][j] => i번째에서 끝나고, 이전이 j인 시퀀스의 최대 누적합
int main() {
ll ans = 0;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int tmp;
cin >> tmp;
arr[i] = tmp;
mm[tmp] = i;
}
for (int i = 1; i < n; i++) {
int cur = arr[i];
for (int j = 0; j < i; j++) {
int prev = arr[j];
ll next = cur + (cur - prev);
if (mm.find(next) != mm.end()) {
int next_idx = mm[next];
dp[next_idx][i] = cur + prev + next;
ans = max(ans, dp[next_idx][i]);
}
}
}
for (int i = 1; i < n; i++) {
int cur = arr[i];
for (int j = 0; j < i; j++) {
if (dp[i][j]) {
int prev = arr[j];
ll next = cur + cur - prev;
if (mm.find(next) != mm.end()) {
int next_idx = mm[next];
dp[next_idx][i] = dp[i][j] + next;
ans = max(ans, dp[next_idx][i]);
}
}
}
}
cout << ans << endl;
return 0;
}
'알고리즘 & Problem Solving > 한국정보올림피아드(KOI)' 카테고리의 다른 글
| [KOI 2007 초등부 3번] 백준 2539번 모자이크 문제 풀이 (0) | 2019.11.26 |
|---|---|
| [KOI 2007 초등부 1번] 백준 1713번 후보 추천하기 문제 풀이 (0) | 2019.11.26 |
| [KOI 2008 초등부 1번] 백준 6986 절사평균 - 문제 풀이 (0) | 2019.11.23 |
| KOI 2010 초등부 문제 풀이 (0) | 2019.09.11 |
| KOI 2018 초등부 문제 풀이 (0) | 2019.08.26 |
