4243 보안 업체 https://www.acmicpc.net/problem/4243
2184 김치 배달 https://www.acmicpc.net/problem/2184
2419 사수아탕 https://www.acmicpc.net/problem/2419
1. 가로등 끄기
어렵지만 좋은문제이다.
현재 로봇이 M위치에 있을 때 모든 가로등을 끄는데 전력의 최소값을 구하는 문제이다.
처음에는 위치와 이동 시간으로 점화식을 세우려 했으나 이동 시간이 무한한값을 가질 수 도
있기때문에 불가능하다.
그래서 점화식을 구간 [L, R]을 탐색(가로등을 껏을때)하고 flag(0 : L, 1 : R)위치에 있을 때
전력의 최솟값으로 나타냈다.
$DP[L][R][0]$ : 구간 [L, R]을 탐색하고 L에 위치한 경우의 전력의 최솟값
$DP[L][R][1]$ : 구간 [L, R]을 탐색하고 R에 위치한 경우의 전력의 최솟값
여기까진 좋았지만 이동 시간의 정보를 어떻게 넣을지 고민하다가 안되는걸 알면서도 sec라는 변수를 재귀함수에 넣어버렸다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 99999999999999
int N, M;
int d[1001], cost[1001];
long long dp[1001][1001][2];
//flag 0 : 왼쪽, 1 : 오른쪽
long long solve(int L, int R, int flag, int sec) {
if (L == 1 && R == N) return 0;
long long &ret = dp[L][R][flag];
if (ret != -1) return ret;
ret = INF;
int nsec;
if (L - 1 >= 1) {
if (!flag) nsec = d[L] - d[L - 1] + sec;
else nsec = d[R] - d[L - 1] + sec;
ret = min(ret, solve(L - 1, R, 0, nsec) + nsec*cost[L - 1]);
}
if (R + 1 <= N) {
if (!flag) nsec = d[R + 1] - d[L] + sec;
else nsec = d[R + 1] - d[R] + sec;
ret = min(ret, solve(L, R + 1, 1, nsec) + nsec*cost[R + 1]);
}
return ret;
}
int main() {
memset(dp, -1, sizeof dp);
scanf("%d%d", &N, &M);
for (int n = 1;n <= N;n++)
scanf("%d%d", &d[n], &cost[n]);
printf("%lld\n", solve(M, M, 0, 0));
return 0;
}
| cs |
이동시간이라는 정보를 어떻게 넣을 수 있을지 고민하다가 메모리적으로 불가능하다고 판단했다.
사실 이전의 이동시간은 필요가 없고 현재 필요한 이동시간만 계산하면 된다.
아직 꺼지지 않은 가로등에 (현재 필요한 이동시간 * 가로등 전력)을 누적합해주면 되기 때문이다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 987654321
int N, M;
int d[1001], cost[1001];
long long sum_cost[1001];
// [L,R]만큼 탐색하고 현재 flag가 0이라면 L위치, 1이라면 R위치에 있을 때
// 낭비되는 전력값의 최소값
long long dp[1001][1001][2];
//flag 0 : 왼쪽, 1 : 오른쪽
long long solve(int L, int R, int flag) {
if (L == 1 && R == N) return 0;
long long &ret = dp[L][R][flag];
if (ret != -1) return ret;
ret = INF;
long long nsec, ncost;
if (L - 1 >= 1) {
if (!flag) nsec = d[L] - d[L - 1];
else nsec = d[R] - d[L - 1];
ncost = nsec * (sum_cost[L - 1] + sum_cost[N] - sum_cost[R]);
ret = min(ret, solve(L - 1, R, 0) + ncost);
}
if (R + 1 <= N) {
if (!flag) nsec = d[R + 1] - d[L];
else nsec = d[R + 1] - d[R];
ncost = nsec*(sum_cost[L - 1] + sum_cost[N] - sum_cost[R]);
ret = min(ret, solve(L, R + 1, 1) + ncost);
}
return ret;
}
int main() {
memset(dp, -1, sizeof dp);
scanf("%d%d", &N, &M);
for (int n = 1;n <= N;n++) {
scanf("%d%d", &d[n], &cost[n]);
sum_cost[n] = sum_cost[n - 1] + cost[n];
}
printf("%lld\n", solve(M, M, 0));
return 0;
}
| cs |
점화식까진 유도했으나 부분문제를 좀더 생각하지 못해서 풀지못했던 아쉬운 문제이다.
2. 보안 업체
거의 똑같은 문제다.
좀더 쉽게 풀기위해 거리들을 좌표들로 바꾼다음에
(아직 방문하지 않은 상점의 갯수 * 방문한 상점들의 거리 합)을 누적시켰다.
4. 사수아탕
2. 보안 업체
거의 똑같은 문제다.
좀더 쉽게 풀기위해 거리들을 좌표들로 바꾼다음에
(아직 방문하지 않은 상점의 갯수 * 방문한 상점들의 거리 합)을 누적시켰다.
#include <cstdio>
#include <cstring>
typedef long long ll;
inline ll min(ll a, ll b) { return a < b ? a : b; }
#define lINF 1e18
int N, S;
ll dp[101][101][2];
ll pos[101];
ll solve(int l, int r, int flag) {
if (l == 1 && r == N) return 0;
ll &ret = dp[l][r][flag];
if (ret != -1) return ret;
ret = lINF;
ll mul = N - r + l - 1, cost;
if (l - 1 >= 1) { //왼쪽으로
if (!flag) cost = mul*(pos[l] - pos[l - 1]); //왼쪽->왼쪽
else cost = mul*(pos[r] - pos[l - 1]); //오른쪽->왼쪽
ret = min(ret, solve(l - 1, r, 0) + cost);
}
if (r + 1 <= N) { //오른쪽으로
if (!flag) cost = mul*(pos[r + 1] - pos[l]); //왼쪽->오른쪽
else cost = mul*(pos[r + 1] - pos[r]); //오른쪽->오른쪽
ret = min(ret, solve(l, r + 1, 1) + cost);
}
return ret;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
memset(dp, -1, sizeof dp);
memset(pos, 0, sizeof pos);
scanf("%d%d", &N, &S);
for (int n = 2;n <= N;n++)
scanf("%lld", &pos[n]), pos[n] += pos[n - 1];
printf("%lld\n", solve(S, S, 0));
}
return 0;
}
| c |
3. 김치 배달
똑같은 문제다.
쉬는 정도 += (남은 김치 * 이동 거리) 로 누적해주면서 최솟값을 찾아주면 된다.
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 987654321
int N, L;
int p[1002];
long long dp[1002][1002][2];
long long solve(int l, int r, int dir) {
if (l == 0 && r == N) return 0;
long long &ret = dp[l][r][dir];
if (ret != -1) return ret;
ret = INF;
long long last = N - (r - l);
if (dir == 0) { //왼쪽에 있음
if (l - 1 >= 0)
ret = min(ret, solve(l - 1, r, 0) + 1LL*last*(p[l] - p[l - 1]));
if (r + 1 <= N)
ret = min(ret, solve(l, r + 1, 1) + 1LL*last*(p[r + 1] - p[l]));
}
else { //오른쪽에 있음
if (l - 1 >= 0)
ret = min(ret, solve(l - 1, r, 0) + 1LL*last*(p[r] - p[l - 1]));
if (r + 1 <= N)
ret = min(ret, solve(l, r + 1, 1) + 1LL*last*(p[r + 1] - p[r]));
}
return ret;
}
int main() {
memset(dp, -1, sizeof dp);
scanf("%d%d", &N, &L);
for (int n = 0;n < N;n++) scanf("%d", &p[n]);
p[N] = L;
sort(p, p + N + 1);
int S = lower_bound(p, p + N + 1, L) - p;
printf("%lld\n", solve(S, S, 0));
return 0;
}
| cs |
4. 사수아탕
사탕바구니에 M개의 사탕들이 N곳에 들어있다.
수아는 0에있으며 1이동할때 사탕들이 1줄어든다.
수아가 얻을 수 있는 최대 사탕의 개수를 구하는 문제다.
처음에 위와같은 유형의 dp로 풀 수 있을것 같다고 생각했지만 복합적인 생각으로 풀지못했다.
이문제는 위에서처럼 모든 N개의 경우를 얻을때 최적값이 아닐 수도 있다.
그러므로 [0, N]개의 사탕주머니를 얻을 때의 경우중 최대값을 구해야한다.
$O(N^3)$으로 문제를 해결할 수 있다.
수아는 0에있으며 1이동할때 사탕들이 1줄어든다.
수아가 얻을 수 있는 최대 사탕의 개수를 구하는 문제다.
처음에 위와같은 유형의 dp로 풀 수 있을것 같다고 생각했지만 복합적인 생각으로 풀지못했다.
이문제는 위에서처럼 모든 N개의 경우를 얻을때 최적값이 아닐 수도 있다.
그러므로 [0, N]개의 사탕주머니를 얻을 때의 경우중 최대값을 구해야한다.
$O(N^3)$으로 문제를 해결할 수 있다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 987654321
int N, M;
int pos[303];
int dp[303][303][2];
int ans = 0;
int solve(int l, int r, int flag, int remain) {
if (remain == 0) return 0;
int &ret = dp[l][r][flag];
if (ret != -1) return ret;
ret = INF;
if (!flag) { //왼쪽
if (l - 1 >= 0) ret = min(ret, solve(l - 1, r, 0, remain - 1) + remain * (pos[l] - pos[l - 1]));
if (r + 1 <= N) ret = min(ret, solve(l, r + 1, 1, remain - 1) + remain * (pos[r + 1] - pos[l]));
}
else { //오른쪽
if (l - 1 >= 0) ret = min(ret, solve(l - 1, r, 0, remain - 1) + remain*(pos[r] - pos[l - 1]));
if (r + 1 <= N) ret = min(ret, solve(l, r + 1, 1, remain - 1) + remain*(pos[r + 1] - pos[r]));
}
return ret;
}
int main() {
scanf("%d%d", &N, &M);
for (int n = 0;n < N;n++) scanf("%d", &pos[n]);
pos[N] = 0;
sort(pos, pos + N + 1);
int start = lower_bound(pos, pos + N + 1, 0) - pos;
for (int n = 0;n <= N;n++) {
memset(dp, -1, sizeof dp);
ans = max(ans, n*M - solve(start, start, 0, n));
}
printf("%d\n", ans);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기