boj 2450 : 모양정돈

boj 2450 : 모양정돈

https://www.acmicpc.net/problem/2450

아이디어는 굉장히 간단하다.

DP로 먼저 접근하다가 시간이 오래걸렸을 뿐....

완전탐색으로 (네모, 세모, 원)의 순열을 찾으면 총 6가지인데, 각각 순열에 대하여 최소이동횟수를 구하면 된다.

최소 이동 횟수를 생각하는 것이 난 조금 어려웠는데..

(i,j) : i위치에 있는 j의 갯수

이렇게 두면

(1,2) - (2,1) >= 0 ? (1,2) + (1,3) + (1,2) - (2,1) + (3,2)

else                    (1,2) + (1,3) + (1,3,) - (3,1) + (2,3)

이렇게 된다.

풀어서 해석하면 1먼저 다 채우고, 2,3을 채운다는 개념.

다른사람의 코드를 보니

(1,2) + (1,3) + max( (2,3) , (3,2) )

.....

어떻게 한거지?

처음에 생각한 것에서 유도할 수는 있다. (2,3) + (2,1) = (1,2) + (3,2) 이므로...

그런데 저 식은 무슨의미일까...?

-> 이해될듯말듯하다.