백준 2618

문제

---

Code

package test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P2618 {
	// N : 도로의 개수, W : 사건의 개수
	static int N, W; 
	
	/*
	dp[i][j] : 
	첫 번째 경찰차의 위치가 x번째 사건이고 두 번째 경찰차의 위치가 y번째 사건에 있을 때 
	현재 위치에서 사건을 끝까지 해결할때 까지 이동하는 거리의 합의 최솟값
	(0 번째 사건일 때 --> 아직 아직 해결 한 사건 없음)
	*/
	
	static int[][] dp = new int[1002][1002];
    
    
	// (eventPosition[i][0], eventPosition[i][1]) : i 번째 사건 발생 좌표
	static int[][] eventPosition = new int[1002][2];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		N = Integer.parseInt(br.readLine());
		W = Integer.parseInt(br.readLine());
		
		// 사건 발생 좌표 입력
		for(int i = 1; i <= W; i++) {
			st = new StringTokenizer(br.readLine());
			eventPosition[i][0] = Integer.parseInt(st.nextToken());
			eventPosition[i][1] = Integer.parseInt(st.nextToken());
		}
		
		// 총 이동 거리
		sb.append(total_min_distance(1, 0, 0)).append('\n');
		
		int oneIdx = 0;
		int twoIdx = 0;
		
		/* 각 사건을 해결한 경찰차 번호 --> 역 추적
		 
		1) 1번 경찰차가 i 번째 사건 해결했다고 가정 --> 1번 경찰차 이동거리 계산
		2) dp에 저장한 다음 사건 지점까지의 이동거리와 1)의 값을 더함
		3 - 1) 계산한 값이 (dp에 저장한) 총 이동거리와 일치하면 --> 1번 경찰차가 해결 
		3 - 2) 계산이 틀리면 2번 경찰차가 해결
		4) 사건 해결한 경찰차 위치를 해결한 사건 지점으로 수정
		5) 반복
		
		*/
        
        
		for(int i = 1; i <= W; i++) {
			// 1)
			int oneDistance = getDistance(1, oneIdx, i);
			
			// 2)
			if(dp[oneIdx][twoIdx] == oneDistance + dp[i][twoIdx]) {
				// 3 - 1)
				oneIdx = i; // 4)
				sb.append(1).append('\n');
			} else {
				// 3 - 2)
				twoIdx = i; // 4)
				sb.append(2).append('\n');
			}
		}
		System.out.println(sb.toString());
	}
    
    
	/*
    total_min_distance : eventIdx 개의 사건을 모두 해결할 때까지의 총 이동거리 최솟값
    
	eventIdx == 1 --> 1번째 사건
	oneIdx : 1번 경찰차가 위치한 사건 번호
	twoIdx : 2번 경찰차가 위치한 사건 번호
	*/
    
    
	private static int total_min_distance(int eventIdx, int oneIdx, int twoIdx) {
		// 사건의 개수가 W보다 많을 때 --> 중단
		if(eventIdx > W) {
			return 0;
		}
		// 이미 계산 한 경우
		if(dp[oneIdx][twoIdx] != 0) {
			return dp[oneIdx][twoIdx];
		}
		
		/*
        oneMoveCount : 1번 경찰차가 사건 해결한 경우 이동거리 최소 값
        
		재귀 --> eventIdx + 1 : 다음 사건 이동
		1번 경찰차는 해결한 사건 위치로(eventIdx) 이동, 2번 경찰차즌 그대로
		*/ 
        
		int oneMoveCount = total_min_distance(eventIdx + 1, eventIdx, twoIdx) + getDistance(1, oneIdx, eventIdx);
		
		/*
        twoMoveCount : 2번 경찰차가 사건 해결한 경우 이동거리 최소값
        
		재귀 --> eventIdx + 1 : 다음 사건 이동
		1번 경찰차는 해결한 사건 위치로(eventIdx) 이동, 2번 경찰차즌 그대로
		*/
        
		int twoMoveCount = total_min_distance(eventIdx + 1, oneIdx, eventIdx) + getDistance(2, twoIdx, eventIdx);
		
        
		// 1번 경찰자와 2번 경찰차의 거리 중 최소
		return dp[oneIdx][twoIdx] = Math.min(oneMoveCount, twoMoveCount);
	}
    
    
	/*
    getDistance : carNum번째 경찰차의 시작지점에서 사건 지점까지 거리 구하기
	carNum : 경찰차 종류(1번 or 2번)
	*/
    
    
	private static int getDistance(int carNum, int startIdx, int endIdx) {
		int[] startPosition = getStartPosition(carNum, startIdx);
		
		return Math.abs(startPosition[0] - eventPosition[endIdx][0]) + 
				Math.abs(startPosition[1] - eventPosition[endIdx][1]);
	}
	
    
    
	/*
    getStartPosition : 현재 위치 구하기
	carNum : 경찰차 종류(1번 or 2번)
	*/
    
    
	private static int[] getStartPosition(int carNum, int idx) {
		// 아직 해결한 사건이 없을 때
		if(idx == 0) {
			// 1번 경찰자
			if(carNum == 1) {
				return new int[] {1,1};
			}
			// 2번 경찰자
			return new int[] {N, N};
		}
		// 이미 사건 해결 --> 마지막으로 해결한 사건 위치
		return eventPosition[idx];
	}

}

---

참고 : https://wellbell.tistory.com/63