[SWEA] 9092 마라톤

 

DP 문제다! 아직도 DP에서 실수가 많다...

완탐으로는 불가능하니까 중복되는 정보를 줄여보자

테이블은 d[현재위치][남은 점프 수]로 잡는다

 

처음에 틀렸던 이유는 이전에 뛰어온 곳을 저장하려고 했기 때문이였다

현재위치만 가지고 다음에 뛰어갈 곳을 구해서 정보를 업데이트하면 되는데

테이블은 이전에 정보를 가지지도 않으면서 나는 이전에 어디서 왔는지 정보를 들고다녔다

처음 테케만 나오고 바로 틀렸따~!

 

틀린 소스코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int INF = 987654321;
int n,k;
int d[505][505];
pair<int,int> point[505];
 
int dist(int x,int y){
    return (abs(point[x].first-point[y].first) + abs(point[x].second-point[y].second));
}
 
int solve(int now,int cnt,int prev){
    if(now==n-1) return dist(prev,now);
    int&ret = d[now][cnt];
    if(ret != -1) return ret;
    ret = INF;
 
    if(cnt==0) ret = (solve(now+1,cnt,now)+dist(now,prev));
    else ret = min(solve(now+1,cnt,now)+dist(now,prev),solve(now+1,cnt-1,prev));
    return ret;
}
 
int main(){
    //freopen("input.txt","r",stdin);
    int tcase; scanf(" %d",&tcase); int c=1;
    while(tcase--){
        memset(point,0,sizeof(point));
        memset(d,-1,sizeof(d));
 
        scanf(" %d %d",&n,&k);
        for(int i=0;i<n;i++) scanf(" %d %d",&point[i].first,&point[i].second);
        printf("#%d %d\n",c++,solve(1,k,0));
    }
}

 

solve 함수에서 prev를 들고다니지만 테이블에는 이 정보를 저장하지 않는다

그리고 약간은 뒤죽박죽이다 식이! 결국 어디가 틀린지 못찾고 다른사람의 코드를 한번 보고 수정했다

 

우선 기준이 내가되면 된다. 내가 뛸 수 있는 칸이 k개면 0~k칸까지 현재 위치에서 뛰어보면 된다

그럼 많이 풀어 본 기본적인 dp문제가 된다ㅠ 연습을 많이해야겠다..!

 

소스코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int INF = 987654321;
int n,k;
int d[505][505];
pair<int,int> point[505];
 
int dist(int x,int y){
    return (abs(point[x].first-point[y].first) + abs(point[x].second-point[y].second));
}
 
int solve(int now,int cnt){
    if(now==n-1) return 0;
    int&ret = d[now][cnt];
    if(ret != -1) return ret;
    ret = INF;
 
    for(int i=0;i<=cnt;i++){
        int next = now+1+i;
        if(next>n-1) continue;
        int dist_next = dist(now,now+1+i);
        ret = min(ret,dist_next+solve(next,cnt-i));
    }
    return ret;
}
 
int main(){
    //freopen("input.txt","r",stdin);
    int tcase; scanf(" %d",&tcase); int c=1;
    while(tcase--){
        memset(point,0,sizeof(point));
        memset(d,-1,sizeof(d));
 
        scanf(" %d %d",&n,&k);
        for(int i=0;i<n;i++) scanf(" %d %d",&point[i].first,&point[i].second);
        printf("#%d %d\n",c++,solve(0,k));
    }
}