[BOJ] 33980 현대모비스 V2X 자율주행 2

문제

1번 차량과 2번 차량이 0 에서 N 까지 이동합니다. 

각 차량은 매 초 R 또는 U 이동 중 하나를 합니다. 

 

두 차량은, 2N의 이동을 하고, 문자열로 주어집니다. 이 때, 한 차량의 이동의 위치를 swap 할 수 있는 연산이 있습니다.

 

두 차량이 겹치지 않도록 이동경로를 구성하는 최소 연산의 횟수를 구하시오.

관찰

두 차량이 겹치지 않게 이동하기 위한 조건을 생각해보자. 특정 시간에서 R 개수와 L 개수가 같으면 안된다.

R이랑 L 은 무조건 N 개씩 있기 때문에, R 이나 L 둘 중 하나만 고려해도 문제에서 필요한 정보를 얻을 수 있다.

 

또한 시작과 끝의 이동은 서로 달라야 한다. 시작에서 같은 이동을 하면 충돌해버린다. 또한, 한 차량의 시작과 끝 이동이 같으면 무조건 충돌이 일어나게 된다. 그렇기 때문에 이를 처리해줘야 한다.

첫 이동이 R이면, 다른 차량보다 항상 R이 더 많아야 하고, L로 끝나야 한다. 반대도 마찬가지다.

일단 R이나 L 둘 중 뭘로 잡든 같기 때문에 쓰기 편한 R로 잡아준다.

 

어느 시점에서 R이 같아진다면 이는 충돌한 것임을 알 수 있다. 그러면 충돌하지 않도록 경로를 옮겨줘야 한다.

 

어떻게 옮겨줘야 할지가 매우 고민이다...

 

RR

UU 일때 뭘 옮겨줘야될까..

 

RU

RU 면 어떻게 옮 -> 이거는 그냥 한번만 옮기면 되네.

 

어떤 시점 t 에서, (1 <= t <= 2N) R 이랑 U 개수를 r 이랑 u 라고 하자. r = t - u 가 된다. 그렇다면 어느 시점에서 r이 2개 차이가 난다고 해보자.
r1 = r2 - 2 이라면 u1 = t - r1 , u2 = t - r2 이다. 둘의 차를 구해보면, r1 과 r2 의 차이와 같음을 볼 수 있다. 그러므로 뭘로 기준을 잡던 차이를 보는데 있어서는 같다. 

또한,  (0,0) 부터 (N,N) 부터 진행되고, R은 x축 을 1만큼 이동, U는 y축을 1만큼 이동.으로 정의되므로, 뒤집더라도 같은 문제를 얻을 수 있다.

그렇다면 R 또는 U 중 하나를 잡은 뒤 각 시점에서 개수의 차이를 계산했을 때, 0 이하가 되는 값들을 본다. 이 값의 절댓값 + 1 이 최소로 바꿔야되는 횟수이다. 

그렇다면 이제 RU, UR 이 되도록  맞춰줘야 한다.. 잘 맞춰줘야 되는데. 흐음. 분기 생각 ㄱㄱ.

바꿀 필요업슨 경우

UR,

RU

 

한번 바꿔야 되는 경우

UR

RR 또는

UR

UR

같이 하나는 만족했지만 나머지 하나가 같거나... 같은 것.

 

이외는 두 번 바꿔야 된다. 두 번 바꾸는 상태에서 하나만 바꾸는 상태로 넘기는게 좋을거 같다.

RR  RR 

UU, RR

RURUUR

RUURUR

112223

111223