BOJ 11983 Radio Contact

https://www.acmicpc.net/problem/11983

11983번: Radio Contact

 

 

이런 유형의 문제를 많이 풀어봐서 풀이가 바로 하나 떠올랐다.

그 풀이는 DP였고, DP라고 확정한 이유는 다음과 같다.
- (John의 step 단계, Bassie의 step 단계) 를 (i,j)라 할 때 해당 단계 이전의 step 은 (i-1,j), (i-1, j-1), (i,j-1) 이다.
- 이 3가지 경우에서 가장 작은 누적 power를 가진 step 에 (i,j)일때 distance를 더한 값이 (i,j) 까지 John과 Bassie가 걸었을 때 드는 power 이다.

이를 통해 얻는 점화식은 다음과 같다.

$$ DP[i][j] = min ( DP[i][j-1], DP[i-1][j-1], DP[i-1][j]) + dist[i][j] $$

따라서 DP라고 확정할 수 있게 되었고, 해당 방식으로 code 를 짰다.

이동 경로에 따른 좌표 들에 대해 전처리만 해주면, 이후는 편하게 풀 수 있다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n,m,fx,fy,bx,by;
vector<pair<int, int>> f, b;
int dp[1001][1001];
void make_vector(vector<pair<int, int>>& v, int x, int y){
    char p[1001];
    scanf("%s",p);
    v.push_back({x, y});
    for(int i=0;p[i];i++){
        switch(p[i]){
        case 'E': x += 1; break;
        case 'W': x -= 1; break;
        case 'N': y += 1; break;
        case 'S': y -= 1; break;
        default: break;
        }
        v.push_back({x, y});
    }
}
int get_distance(const pair<int, int>& a, const pair<int, int>& b){
    return (a.first - b.first)*(a.first - b.first) + (a.second - b.second)*(a.second - b.second);
}
int main(){
    scanf("%d%d%d%d%d%d",&n,&m,&fx,&fy,&bx,&by);
    make_vector(f,fx,fy);
    make_vector(b,bx,by);
    for(int i=1;i<f.size();i++) dp[i][0] = dp[i-1][0] + get_distance(b[0], f[i]);
    for(int i=1;i<b.size();i++) dp[0][i] = dp[0][i-1] + get_distance(b[i], f[0]);

    for(int i=1;i<f.size();i++){
        for(int j=1;j<b.size();j++){
            int dist = get_distance(f[i], b[j]);
            dp[i][j] = min(dp[i-1][j] + dist, dp[i][j-1] + dist);
            dp[i][j] = min(dp[i-1][j-1] + dist, dp[i][j]);
        }
    }

    printf("%d\n",dp[f.size()-1][b.size()-1]);
    return 0;
}