본문 바로가기

알고리즘 관련/BOJ

BOJ)11983 Radio Contact

문제: icpc.me/11983


파머존과 소가 움직이는 경로가 주어질 때 파머존만 움직이거나 소만 움직이거나 둘이 동시에 움직일수 있다.


이동 후 둘의 거리의 제곱에 비례하게 라디오의 에너지가 소모될 때 파머존과 소가 목적지에 도착했을 때 소모된 라디오 에너지의 최솟값을 출력하는 문제이다.


우리는 이 문제를 다이나믹 프로그래밍을 통하여 해결할 수 있다.


dp[x][y]의 정의는 Farmer John이 X번 이동한 위치이고 소가 Y번 이동한 위치일 때까지 소모된 라디오 에너지의 최솟값이다.


점화식은 dp[x][y]=min(dp[x-1][y],dp[x][y-1],dp[x-1][y-1])+dist(FJx ,COWy)가 되겠다.


파머존과 소가 한번도 움직이지 않았을 때는 에너지 소모가 없다고 하니 기저는 dp[0][0]=0이 된다.


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
36
37
38
39
40
41
42
43
#include <cstdio>
#include <algorithm>
#include <map>
#include <cstring>
#define MAX_N 1000
#define INF 2100000000
using namespace std;
int dp[MAX_N + 1][MAX_N + 1], n, m;
pair<intint> nx[MAX_N + 1], ny[MAX_N + 1];
char mx[MAX_N], my[MAX_N];
int dx[] = { 0,0,1,-};
int dy[] = { 1,-1,0,};
map<charint> mp;
int dist(pair<intint> x, pair<intint> y) {
    return (x.first - y.first)*(x.first - y.first) + (x.second - y.second)*(x.second - y.second);
}
int func(int x, int y) {
    if (x < || y < 0)return INF;
    if (x == && y == 0)return 0;
    int &ret = dp[x][y];
    if (ret != -1)return ret;
    return ret = min(func(x - 1, y), min(func(x, y - 1), func(x - 1, y - 1))) + dist(nx[x], ny[y]);
}
int main() {
    mp['N'= 0;
    mp['S'= 1;
    mp['E'= 2;
    mp['W'= 3;
    scanf("%d%d"&n, &m);
    scanf("%d%d%d%d"&nx[0].first, &nx[0].second, &ny[0].first, &ny[0].second);
    scanf("%s%s"&mx, &my);
    for (int i = 0; i < n; i++) {
        nx[i + 1].first = nx[i].first + dx[mp[mx[i]]];
        nx[i + 1].second = nx[i].second + dy[mp[mx[i]]];
    }
    for (int i = 0; i < m; i++) {
        ny[i + 1].first = ny[i].first + dx[mp[my[i]]];
        ny[i + 1].second = ny[i].second + dy[mp[my[i]]];
    }
    memset(dp, -1sizeof(dp));
    printf("%d\n", func(n, m));
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)2150 Strongly Connected Component  (0) 2017.01.21
BOJ)3176 도로 네트워크  (0) 2017.01.21
BOJ)1766 문제집  (0) 2017.01.20
BOJ)2623 음악프로그램  (3) 2017.01.20
BOJ)11438 LCA 2  (0) 2017.01.19