다이나믹 프로그래밍 위주로 한 번 풀어보았다.
백준 2618번: 경찰차
경찰창의 위치와 각 위치일 때 그 위치가 될 때까지 이동한 거리의 최솟값을 저장해놓으면 된다.
나는 빡대가리같이 map을 써서 코드를 짰다. 굉장히 똥코드지만.. 뭐 통과만 하면 됐지
정석 방법은 각 위치를 1~1000번 번호를 붙여준 뒤 2차원 배열에 저장하는 방법이다.
문제가 치사하게 경로까지 출력해야 하기 때문에 아마 거리, 직전 위치 2가지는 저장해야 한다.
#include <iostream>
#include <vector>
#include <map>
using namespace std;
typedef pair<int, int> ii;
int dist(int a, int b) {
return abs(a / 10000 - b / 10000) + abs(a % 10000 - b % 10000);
}
struct info {
int d;
int now;
info* prev;
info() {}
info(int d, int now, info* prev) : d(d), now(now), prev(prev) {}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, w;
cin >> n >> w;
vector<int> loc(w);
int x, y;
for (int i = 0; i < w; ++i) {
cin >> x >> y;
loc[i] = x * 10000 + y;
}
vector<map<ii, info>> mem(w + 1);
mem[0][ii(10001, n * 10000 + n)] = info(0, 0, nullptr);
for (int i = 0; i < w; ++i) {
for (auto it = mem[i].begin(); it != mem[i].end(); ++it) {
x = it->first.first;
y = it->first.second;
ii next = ii(loc[i], y);
if (mem[i + 1].count(next)) {
int nowd = it->second.d + dist(x, loc[i]);
if (mem[i + 1][next].d > nowd) {
mem[i + 1][next] = info(nowd, 1, &it->second);
}
}
else mem[i + 1][next] = info(it->second.d + dist(x, loc[i]), 1, &it->second);
next = ii(x, loc[i]);
if (mem[i + 1].count(next)) {
int nowd = it->second.d + dist(y, loc[i]);
if (mem[i + 1][next].d > nowd) {
mem[i + 1][next] = info(nowd, 2, &it->second);
}
}
else mem[i + 1][next] = info(it->second.d + dist(y, loc[i]), 2, &it->second);
}
}
int ans = 987654321;
vector<int> order;
info* now;
for (auto it = mem[w].begin(); it != mem[w].end(); ++it) {
if (it->second.d < ans) {
ans = it->second.d;
now = &it->second;
}
}
while (now->prev) {
order.push_back(now->now);
now = now->prev;
}
cout << ans << '\n';
for (int i = w - 1; i >= 0; --i) cout << order[i] << '\n';
}
백준 1315번: RPG
오늘 나의 멘탈을 아작낸 문제.. 쉬운건데 자꾸 이러니까 하루에 한 문제밖에 못 푼다.. 울고 싶다.
처음에 문제 조건의 or 조건을 and로 봐서 시간을 조금 날리고.. 다시 풀었는데 맞왜틀의 정말 화려한 향연이 펼쳐졌다.
결론은 틀린 이유는 약간의 알고리즘 오류.. 자면서 반성해야겠다.
원래는 그림까지는 안그리는데 slack에 질문하느라 그림까지 그렸으니 아까워서 올린다.
(STR, INT) = (m, n)일 때의 최선의 상태는 STR[i] <= m, STR[i] <= n인 모든 퀘스트를 다 깬 상태다.
이 상태에서 남은 PNT를 구할 수 있으니(하나로 결정된다) 포인트가 1 이상 남아있다면 STR 또는 INT에 하나씩 올리면서 상태를 업데이트해주면 된다.
STR을 올리면 그림의 빨간색 부분 퀘스트를 새로 깨게 되므로 빨간색 영역에 해당하는 PNT를 늘려주면 되고, INT를 올리면 파란색 부분을 늘려주면 된다.
문제에서 구하려는 것은 클리어한 퀘스트의 최대 갯수이므로, 이를 각 상태마다 max해 주어야 하는데, (전체 퀘스트의 갯수 - 못 깬 퀘스트의 갯수)로 쉽게 구할 수 있다. 모양은 그림의 검정색 영역처럼 되는데, 이는 2차원 배열로 쉽게 구할 수 있다.
#include <iostream>
#include <memory.h>
using namespace std;
int STR[1010][1010], INT[1010][1010], PNT[1010][1010], cnt[1010][1010];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int S, I, P;
int oneone = 0;
for (int i = 0; i < n; ++i) {
cin >> S >> I >> P;
cnt[I][S]++;
PNT[I][S] += P;
if (S == 1 || I == 1) oneone += P;
}
for (int i = 1000; i >= 1; --i) {
for (int j = 1000; j >= 1; --j) {
STR[i][j] = STR[i + 1][j] + PNT[i][j];
INT[i][j] = INT[i][j + 1] + PNT[i][j];
cnt[i][j] = cnt[i + 1][j] + cnt[i][j + 1] - cnt[i + 1][j + 1] + cnt[i][j];
}
}
memset(PNT, -1, sizeof(PNT));
PNT[1][1] = oneone;
int ans = 0;
for (int i = 1; i <= 1000; ++i) {
for (int j = 1; j <= 1000; ++j) {
if (PNT[i][j - 1] > 0) PNT[i][j] = max(PNT[i][j], PNT[i][j - 1] - 1 + STR[i + 1][j]);
if (PNT[i - 1][j] > 0) PNT[i][j] = max(PNT[i][j], PNT[i - 1][j] - 1 + INT[i][j + 1]);
if (PNT[i][j] != -1) ans = max(ans, n - cnt[i + 1][j + 1]);
}
}
cout << ans << '\n';
}
