모든 도로에는 도로 번호가 있으며 남북방향 도로는 왼쪽부터 1에서 시작하여 N까지 번호가 할당되어 있고 동서방향 도로는 위부터 1에서 시작하여 N까지 번호가 할당되어 있다. 또한 동서방향 도로 사이의 거리와 남 북방향 도로 사이의 거리는 모두 1이다. 동서방향 도로와 남북방향 도로가 교차하는 교차로의 위치는 두 도로의 번호의 쌍인 (동서방향 도로 번호, 남북방향 도로 번호)로 나타낸다. N이 6인 경우의 예를 들면 다음과 같다.
이 도시에는 두 대의 경찰차가 있으며 두 차를 경찰차1과 경찰차2로 부른다. 처음에는 항상 경찰차1은 (1, 1)의 위치에 있고 경찰차2는 (N, N)의 위치에 있다. 경찰 본부에서는 처리할 사건이 있으면 그 사건이 발생된 위치를 두 대의 경찰차 중 하나에 알려 주고, 연락 받은 경찰차는 그 위치로 가장 빠른 길을 통해 이동하여 사건을 처리한다. (하나의 사건은 한 대의 경찰차가 처리한다.) 그리고 사건을 처리 한 경찰차는 경찰 본부로부터 다음 연락이 올 때까지 처리한 사건이 발생한 위치에서 기다린다. 경찰 본부에서는 사건이 발생한 순서대로 두 대의 경찰차에 맡기려고 한다. 처리해야 될 사건들은 항상 교차로에서 발생하며 경찰 본부에서는 이러한 사건들을 나누어 두 대의 경찰차에 맡기되, 두 대의 경찰차들이 이동하는 거리의 합을 최소화 하도록 사건을 맡기려고 한다.
예를 들어 앞의 그림처럼 N=6인 경우, 처리해야 하는 사건들이 3개 있고 그 사건들이 발생된 위치 를 순서대로 (3, 5), (5, 5), (2, 3)이라고 하자. (3, 5)의 사건을 경찰차2에 맡기고 (5, 5)의 사건도 경찰차2에 맡기며, (2, 3)의 사건을 경찰차1에 맡기면 두 차가 이동한 거리의 합은 4 + 2 + 3 = 9가 되 고, 더 이상 줄일 수는 없다.
처리해야 할 사건들이 순서대로 주어질 때, 두 대의 경찰차가 이동하는 거리의 합을 최소화 하도록 사건들을 맡기는 프로그램을 작성하시오.
첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 사건이 발생된 위치가 한 줄에 하나씩 주어진다. 경찰차들은 이 사건들을 주어진 순서대로 처리해야 한다. 각 위치는 동서방향 도로 번호를 나타내는 정수와 남북방향 도로 번호를 나타내는 정수로 주어지며 두 정수 사이에는 빈칸이 하나 있다. 두 사건이 발생한 위치가 같을 수 있다.
출력
첫째 줄에 두 경찰차가 이동한 총 거리를 출력한다. 둘째 줄부터 시작하여 (i+1)번째 줄에 i(1 ≤ i ≤ W)번째 사건이 맡겨진 경찰차 번호 1 또는 2를 출력한다.
입력 예시
6
3
3 5
5 5
2 3
출력 예시
9
2
2
1
풀이
DP 문제. 좌표를 기준으로 생각하는 함정에 빠지면 최소 3차원 이상이 요구된다(경찰차 1의 좌표, 경찰차 2의 좌표...) 따라서 '두 경찰차가 마지막으로 맡은 사건 인덱스'를 기준으로 문제를 재구성해보자. 그렇다면 DP 배열은 (W+1, W+1)크기의 이차원 배열이 된다.
DP(idx1, idx2)에 대해서, 경찰이 맡아야 할 다음 인덱스는 max(idx1, idx2) + 1이 된다(사건이 순서대로 해결되어야 한다는 점에 유의하라). 따라서 idx1의 경찰차 1이 해결하는 경우와 idx2의 경찰차 2가 해결하는 경우, 두 가지 가능성이 존재하며, 둘 중 최소 비용을 저장하여 부분 최적해를 구할 수 있겠다. 이 때 (dfs로 재귀적으로 구한 값 + 다음 인덱스와 지정 인덱스간의 거리값)이 다음 거리 비용이 되므로 이를 참조하여 최소값을 저장하자. 또한 백트래킹을 본 문제에서 요구하는데, 본인 같은 경우는 비트마스킹을 통해 메모리 초과를 피했다.
풀이 코드
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
MAX = float('inf')
N = int(input())
W = int(input())
case_list = [list(map(int, input().split())) for _ in range(W)]
dp = [[[MAX, ''] for _ in range(W+1)] for _ in range(W+1)]
def dfs(idx1, idx2) :
if idx1 == W or idx2 == W :
return (0, 1)
if dp[idx1][idx2][0] < MAX :
return dp[idx1][idx2]
nxt_idx = max(idx1, idx2) + 1
nx, ny = case_list[nxt_idx-1]
cx, cy = case_list[idx1-1] if idx1 > 0 else (1, 1)
tmp, track = dfs(nxt_idx, idx2)
tmp += abs(nx - cx) + abs(ny - cy)
if tmp < dp[idx1][idx2][0] :
dp[idx1][idx2] = (tmp, track * 2)
cx, cy = case_list[idx2-1] if idx2 > 0 else (N, N)
tmp, track = dfs(idx1, nxt_idx)
tmp += abs(nx - cx) + abs(ny - cy)
if tmp < dp[idx1][idx2][0] :
dp[idx1][idx2] = (tmp, track * 2 + 1)
return dp[idx1][idx2]
result, track = dfs(0, 0)
print(result)
for i in range(W) :
print(2 if track & (1 << i) else 1)
