백준온라인 2618번 [경찰차][C++]

www.acmicpc.net/problem/2618

2618번: 경찰차

---

나의 풀이

 

이문제는  DP로 푸는 방법을 생각해야 한다

DP로 생각할 수 있는 근거는  특정 상태  1번 경찰차가 움직였거나 2번 경찰차가 움직인 경우 두 가지밖에 없기 때문에  그 두가지 action에 따른 최소의 cost만 기억해주면 된다.  (특정 상태에서 최솟값은 이전 상태의 최솟값을 이용해 구해야 되는 논리가 나오게 되므로)

 

두대의 경찰차에 대하여 주어진 좌표 순으로 사건을 해결해야 하므로 처음에는 d [1x][1y][2x][2y]로 해결해야 되는 줄 알았지만

어느 경찰차가 어느 사건을 최종적으로 해결했는지만 기억해내면 좌표는 굳이 저장할 필요가 없다.

 

dp 배열 정의

\( DP [i][j]\)   1번 경찰차가 가장 최근 해결한 사건이 i사건이고 2번 경찰차가 가장 최근 해결한 사건이 j 사건일 경우 최소 비용

 

이렇게 되면 다음과 같은 점화식이 나오게 된다

\( DP[i][j] = min (DP [next][j] + dist(i, next) , DP [i][next] + dist(j, next)) \)

 여기서 next 즉 다음 해결해야 되는 사건은 \(max(i, j)+1\) 로 구할 수 있다.

dist는 미리 기억해둔 특정 사건번호의 좌표 번호들의 배열을 이용하여 맨해튼 거리로 계산하면 된다.

    (참고로 이런 방식으로 점화식을 정의할 경우 두 경찰차의 처음 위치에 대한 예외처리는 해줘야 된다)

 

 

출력해야 될 최소 비용과 더불어 어느 경찰차가 사건을 해결했는지 순서대로 출력하기 위해 

\(p [i][j]\)를 두어 어느 경찰차가 이동하는 게 최소비용인지 1 또는 2로 저장을 해주면 된다.

 

 

참고로 이문제의 배열은 중간중간에 의미가 없는 공간이 있다.

즉 거쳐가지 않는 구간이 있다는 말이다.

예를 들어 \(DP [3][3]\)과 같이 두 경찰차가 모두 3번 사건이 발생한 지점에 동시에 공존할 이유가 없다.

 

따라서 이 문제는 bottom으로 풀기 매~~ 우 어렵다는 생각이 든다 저렇게 고려하면 안 되는 경우를 생각하기가 쉽지 않고. 어디서부터 순회를 해야 될지도 정확하게 감이 안 온다 (대충 2차원 배열에서 오른쪽 아래 기준으로 한 겹씩 순회하면 될 거 같은 느낌이긴 한데. 정확하지 않다 )

 

---

소스