경찰차
http://koistudy.net/?mid=prob_page&NO=340
경찰차2
http://koistudy.net/?mid=prob_page&NO=770
이 문제는 이차원 dp문제로 i,j 가 각각 경찰차의 위치가 되는 특이한 유형의 문제다. 이런 비슷한 유형으로는 공주 구하기라는 문제가 있다.
Prob No.0134 : 공주 구하기 [CH04.2.Competition(KOI08Hs-R)]
http://koistudy.net/?mid=prob_page&NO=308
이건 공주에게 가는 마리오와 출발 지점으로 돌아오는 마리오를 i,j로 두고 풀면 된다.
경찰차 solution
dp[i][j]는 경찰차1이 i번째 사건에 있고 경찰차 2가 j번째 사건에 있고 (i!=j), max(i,j) 사건까지 다 해결됬다고 했을 때 이동 경로의 최솟값.
D(x,y)는 x번째 사건과 y번째 사건 위치의 택시 거리라 하자.
dp[i][j] = dp[i-1][j] + D(i-1,i) (i>j & i!=j+1)
dp[i][j] = dp[k][j] + D(k,i) for all k < j (i>j & i=j+1)
dp[i][j] = dp[i][j-1] + D(j-1,j) (i<j & i+1!=j)
dp[i][j] = dp[i][k] + D(k,j) for all k < i (i<j & i+1=j)
dp[i][j] = INFITE (otherwise)
정답은 dp[m][k],dp[k][m] for all 1<=k<=m 중 최솟값이 정답이다.
경찰차 1,경찰차2가 처음에 서로 다른 위치에 있으므로가상의 -1,0 번째 사건을 만들어 경찰차1이 -1번째 사건(1,1)에 경찰차 2가 0번째 사건(n,n)에 있다고 풀면 깔끔히 해결된다.시간 복잡도 : O(m^2)
-------------------------------------------------------------------------------------------------------------------------
경찰차 2 solution
이 문제는 "경찰차"의 발전형 문제로 실제 정보올림피아드 대회에선 꼭 사전순 경로가 아닌 아무 경로나 출력해도 정답이였다.
곰곰히 생각해보면 dp를 거꾸로 돌려보면 쉽게 해결된다.dp를 정방향으로 돌리면서 최솟값이 같다면 경찰차2보다 경찰차1이 우선되도록 짜면 바로 앞에 있는 문자는 사전순이 되지만 크게보면 사전순이 아닐 수 있다.
따라서 dp를 거꾸로 돌려리면서 최솟값이 같다면 경찰차2보다 경찰차1이 우선 되도록 짜면 사전순이면서 값이 최소가 된다.
n번째 사건이 해결된 dp[m][i],dp[i][m](for all 1<=i<=m) 부터 시작해서 1번쩨 사건 해결 전까지 dp 테이블를 작성하면 된다.
곰곰히 생각해보면 dp를 거꾸로 돌려보면 쉽게 해결된다.dp를 정방향으로 돌리면서 최솟값이 같다면 경찰차2보다 경찰차1이 우선되도록 짜면 바로 앞에 있는 문자는 사전순이 되지만 크게보면 사전순이 아닐 수 있다.
따라서 dp를 거꾸로 돌려리면서 최솟값이 같다면 경찰차2보다 경찰차1이 우선 되도록 짜면 사전순이면서 값이 최소가 된다.
n번째 사건이 해결된 dp[m][i],dp[i][m](for all 1<=i<=m) 부터 시작해서 1번쩨 사건 해결 전까지 dp 테이블를 작성하면 된다.
경로추적은
path라는 테이블 배열을 만들어 dp테이블이 갱신될때 그 값이 어디서 좌표에서 온 값인지 적어주면 된다.
댓글 없음:
댓글 쓰기