글 읽기 - 경찰차 문제 질문입니다..

sksdong1 8년 전 0

dp[i] = i번 사건까지 일어났을 때의 최소거리의 합 으로 두고 풀었는데요

틀린부분을 못찾겠네요 ..

혹시 위치가 같을 때 처리방법이 다른가요??

3 3을 입력으로 줬을 때

처리방법에 따라서

4 1 또는 4 2로 답이 나뉘는데 어떻게 해야하는지.

import java.util.Scanner;

class Main{
	static int n,w,a,b,d[][],dp[],car[]; 
	static XY c1,c2;
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		n=sc.nextInt();
		w=sc.nextInt();
		d = new int[w+1][2];
		for(int i=1;i<=w;i++)
			for(int j=0;j<2;j++)
				d[i][j]=sc.nextInt();
		dp = new int[w+1];
		car = new int[w+1];
		c1 = new XY(1,1);
		c2 = new XY(n,n);
		
		for(int i=1;i<=w;i++){ 
			int car1Dist = Math.abs(d[i][0]-c1.x)+Math.abs(d[i][1]-c1.y);
			int car2Dist = Math.abs(d[i][0]-c2.x)+Math.abs(d[i][1]-c2.y);
			int res = car1Dist-car2Dist;
			//car1,car2에서 사건지점 최단거리 구해서 
			
			if(res>=0){ //2가 최단거리인 경우
				dp[i]=dp[i-1]+car2Dist; //최소값 
				car[i]=2;
				c2 = new XY(d[i][0],d[i][1]); //좌표 갱신
			}
			else{
				dp[i]=dp[i-1]+car1Dist;
				car[i]=1;
				c1 = new XY(d[i][0],d[i][1]);
			}
		}
		System.out.println(dp[w]);
		for(int i=1;i<=w;i++){
			System.out.println(car[i]);
		}
	}
}

class XY{
	int x;int y;
	XY(int x,int y){
		this.x=x;this.y=y;
	}
}

Nada 8년 전 0

스페셜 저지이기 때문에

가능한거 아무거나 출력해도 됩니다.

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

문제

문제

출처

ICPC

경찰차 문제 질문입니다..

sksdong1 8년 전 0

Nada 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말