글 읽기 - dp로 풀어봤습니다. 반례 있을까요?

ljs921026 4년 전 0

dp로 풀었습니다.

경찰차1과 다음 목적지 간의 거리, 경찰차 2와 다음 목적지간의 거리

로 메모이제이션을 했구요,

각 경우에서 경찰차1이 이동했을 경우, 경찰차2가 이동했을 경우로 나누어 dp메소드를 구현했습니다.

이후 선택경로를 반환하는 reconstruct에서는 선택의 경우에서 dp메소드의 결과값을 비교하여 더 작은 경로를 반환하는 쪽으로 값을 출력하도록 했습니다.

게시판의 반례도 맞다고 나오는데

혹시 다른 반례가 더 있을까요?

import java.util.*;
import java.io.*;

public class Main {
	static int n;
	static int w;
	static int[][] cache;
	static Pair[] Incident;
	static int[] Dist;
	static int max=987654321;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=null;
		
		n=Integer.parseInt(br.readLine());
		w=Integer.parseInt(br.readLine());
		cache=new int[n*2][n*2];
		for(int j=0;j<n*2;j++) {
			Arrays.fill(cache[j], -1);
		}

		
		Incident=new Pair[w+1];
		for(int i=0;i<w;i++) {
			st=new StringTokenizer(br.readLine());
			int y=Integer.parseInt(st.nextToken());
			int x=Integer.parseInt(st.nextToken());
			Incident[i]=new Pair(y,x);
		}

		Pair Police1=new Pair(1,1);
		Pair Police2=new Pair(n,n);
		System.out.println(minDistance(1,Police1,Police2));
		reconstruct(1,Police1,Police2);
	}
	
	public static int dist(Pair start,Pair end) {
		//두 점간 거리 구하는 메소드
		return Math.abs(start.y-end.y)+Math.abs(start.x-end.x);
	}
	
	public static int minDistance(int num,Pair Police1,Pair Police2) {
		if(num>w)
			return 0;
		
		int dist1=dist(Police1,Incident[num-1]);
		int dist2=dist(Police2,Incident[num-1]);
		if(cache[dist1][dist2]!=-1)
			return cache[dist1][dist2];
		
		cache[dist1][dist2]=max;
		if(num<=w) {
			cache[dist1][dist2]=Math.min(cache[dist1][dist2],minDistance(num+1,Incident[num-1],Police2)+dist(Police1,Incident[num-1]));
			cache[dist1][dist2]=Math.min(cache[dist1][dist2],minDistance(num+1,Police1,Incident[num-1])+dist(Police2,Incident[num-1]));
		}
		return cache[dist1][dist2];
	}
	
	public static void reconstruct(int num,Pair Police1,Pair Police2) {
		if(num>w)
			return;
		
		if(minDistance(num+1,Incident[num-1],Police2)+dist(Police1,Incident[num-1])>minDistance(num+1,Police1,Incident[num-1])+dist(Police2,Incident[num-1])) {
			System.out.println(2);
			reconstruct(num+1,Police1,Incident[num-1]);
		}else {
			System.out.println(1);
			reconstruct(num+1,Incident[num-1],Police2);
		}
	}
}

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

ljs921026 4년 전 0

문제의 정의를 좀 바꿔서

dp메소드를 경찰차1이 마지막으로 해결한 사건, 경찰차 2가 마지막으로 해결한 사건을 매개변수로 하여

총 최소이동거리를 반환하도록 구현했습니다.

근데 런타임오류가뜨네요ㅠ

어디가 문제인지 모르겠어서 질문 올립니다.

import java.util.*;
import java.io.*;

public class Main {
	static int n;
	static int w;
	static int[][] cache;
	static Pair[] Incident;
	static int[] Dist;
	static int max=987654321;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=null;
		
		n=Integer.parseInt(br.readLine());//n입력
		w=Integer.parseInt(br.readLine());//w입력
		cache=new int[n*2][n*2];
		for(int j=0;j<n*2;j++) {
			Arrays.fill(cache[j], -1);
		}
		
		Incident=new Pair[w+1];
		for(int i=0;i<w;i++) {
			st=new StringTokenizer(br.readLine());
			int y=Integer.parseInt(st.nextToken());
			int x=Integer.parseInt(st.nextToken());
			Incident[i]=new Pair(y,x);
		}

		System.out.println(minDistance(0,0));
		reconstruct(0,0,0);
	}
	
	public static int dist(Pair start,Pair end) {
		//두 점간 거리 구하는 메소드
		return Math.abs(start.y-end.y)+Math.abs(start.x-end.x);
	}
	
	public static int minDistance(int Police1, int Police2) {
		if(Police1==w||Police2==w)
			return 0;
		
		if(cache[Police1][Police2]!=-1)
			return cache[Police1][Police2];
		
		int next=Math.max(Police1, Police2)+1;
		int nextone=0;//1을 선택할 시 1이 움직여야 할 거리
		int nexttwo=0;//2를 선택할 시 2가 움직여야 할 거리
		if(Police1==0)
			nextone=dist(new Pair(1,1),Incident[next-1]);//(1,1)에서 다음 사건까지의 거리
		else
			nextone=dist(Incident[Police1-1],Incident[next-1]);//Police1위치에서 다음 사건까지의 거리
		if(Police2==0)
			nexttwo=dist(new Pair(n,n),Incident[next-1]);//(n,n)에서 다음 사건까지의 거리
		else
			nexttwo=dist(Incident[Police2-1],Incident[next-1]);//Police2위치에서 다음 사건까지의 거리
		
		cache[Police1][Police2]=max;
		cache[Police1][Police2]=Math.min(cache[Police1][Police2],minDistance(next,Police2)+nextone);//1을 선택했을 경우
		cache[Police1][Police2]=Math.min(cache[Police1][Police2],minDistance(Police1,next)+nexttwo);//2를 선택했을 경우
		return cache[Police1][Police2];
	}
	
	public static void reconstruct(int num,int Police1,int Police2) {
		if(num==w)
			return;
		
		int next=Math.max(Police1, Police2)+1;
		int nextone=0;//1을 선택할 시 1이 움직여야 할 거리
		int nexttwo=0;//2를 선택할 시 2가 움직여야 할 거리
		if(Police1==0)
			nextone=dist(new Pair(1,1),Incident[next-1]);//(1,1)에서 다음 사건까지의 거리
		else
			nextone=dist(Incident[Police1-1],Incident[next-1]);//Police1위치에서 다음 사건까지의 거리
		if(Police2==0)
			nexttwo=dist(new Pair(n,n),Incident[next-1]);//(n,n)에서 다음 사건까지의 거리
		else
			nexttwo=dist(Incident[Police2-1],Incident[next-1]);//Police2위치에서 다음 사건까지의 거리
		
		if(minDistance(next,Police2)+nextone>=minDistance(Police1,next)+nexttwo) {
			System.out.println(2);
			reconstruct(num+1,Police1,next);
		}else {
			System.out.println(1);
			reconstruct(num+1,next,Police2);
		}
	}
}

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

ljs921026 4년 전 0

cache배열을 잘못 선언했었네요 해결했습니다.

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

문제

문제

출처

ICPC

dp로 풀어봤습니다. 반례 있을까요?

ljs921026 4년 전 0

ljs921026 4년 전 0

ljs921026 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말