백트래킹1 BOJ2618 경찰차 BOJ2618 경찰차 dp[ i ][ j ] dist = 마지막으로 A, B가 각각 i, j를 처리했을 때 움직인 총 거리 T = 가장 최근 사건을 처리하기 직전의 상태 STEP 1. w=1일 때 dp[ 1 ][ 0 ], dp[ 0 ][ 1 ] 갱신한다. STEP 2. w=2~W일 때 dp[ * ][ w ]와 dp[ w ][ * ]를 구한다. w-1번째, w번째 사건을 처리하는 경찰차가 각각 무엇인지에 따라 구해주면 된다. A-A: [ w-1 ][ * ] → [ w ][ * ] A-B: [ w-1 ][ * ] → [ w-1 ][ w ] B-A: [ * ][ w-1 ] → [ w ][ w-1 ] B-B: [ * ][ w-1 ] → [ * ][ w ] ㆍ*에 들어갈 수는 0부터 w-2까지여야 한다. ㆍdis.. 2021. 1. 29. 이전 1 다음