글 읽기 - [c++] 틀린 이유를 도저히 모르겠습니다....

jungby1 4년 전 0

min_dist함수로 최소거리 구하고, tracking함수로 경찰차가 간 순서를 구했습니다. 여기 질문에 있는 반례도 다 넣어봤는데 다 맞게 나왔습니다. 그런데도

틀렸다고 나오는건 분명 이 코드에 논리적인 오류가 있어서겠죠??ㅠㅠ 고수님들 도와주십시오

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define inf 987654321

int pos[1001][2], init[2][2], max_w;
int dp[1001][1001], track[1001];

int dist(int a[], int b[]);
int min_dist(int w, int a, int b);
int tracking(int w, int a, int b); 

int main() {
	
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, w;
	cin >> n >> w; 
	memset(dp,-1,sizeof(dp)), max_w=w;
	
	for(int i=1; i<=w; i++){
		cin >> pos[i][0] >> pos[i][1];
	}
	init[0][0]=1, init[0][1]=1, init[1][0]=n,init[1][1]=n;
	
	min_dist(0,0,0);
	cout<<dp[0][0]<<"\n";
	tracking(0,0,0);
	for(int i=1; i<=w; i++) cout<<track[i]<<"\n";
	return 0;
}
int dist(int a[], int b[]){
	int ret= a[0]+a[1]-b[0]-b[1];
	if(ret<0) ret -= ret*2; 
	return ret;
}

int min_dist(int w, int a, int b){
	
	int &ret= dp[a][b];
	if(ret!=-1) return ret;
	if(a==max_w || b==max_w) {ret=0; return 0;}
	ret=inf;
	
	if(a==0) {
		ret=min(ret, min_dist(w+1,w+1,b)+dist(pos[w+1],init[0]));	
		if(b==0) ret=min(ret, min_dist(w+1,a,w+1)+dist(pos[w+1],init[1]));
		else if(b!=0) ret=min(ret, min_dist(w+1,a,w+1)+dist(pos[w+1],pos[b]));
	}
	else if(a!=0) {
		ret=min(ret, min_dist(w+1,w+1,b)+dist(pos[w+1],pos[a]));
		if(b==0) ret=min(ret, min_dist(w+1,a,w+1)+dist(pos[w+1],init[1]));
		else if(b!=0) ret=min(ret, min_dist(w+1,a,w+1)+dist(pos[w+1],pos[b]));
	}
	
	return ret;
}

int tracking(int w, int a, int b){
	
	if(a==max_w || b==max_w) return 0;
	int n, m;
	
	if(a==0) n=dp[w+1][b]+dist(pos[w+1],init[0]);
	else n=dp[w+1][b]+dist(pos[w+1],pos[a]);
	
	if(b==0) m=dp[a][w+1]+dist(pos[w+1],init[1]);
	else m=dp[a][w+1]+dist(pos[w+1],pos[b]);
	
	if(n>m){
		track[w+1]=2;
		tracking(w+1,a,w+1);
	}
	else{
		track[w+1]=1;
		tracking(w+1,w+1,b);
	}
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[c++] 틀린 이유를 도저히 모르겠습니다....

jungby1 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말