BOJ 2834 - 박스 정렬
permutation cycle decomposition에서도 상당히 어려운 문제이고 난이도가 P4 는 되야 한다고 생각한다.
우선 로봇의 동작은 어떤 임의의 수들을 골라서 임의의 순서로 cycle을 만들어 한 번 회전시키는 것이다.
permutation cycle대로 묶어보자. 그럼 그것들을 한 번의 명령으로 모두 제자리에 가도록 해줄 수 있다.
그럼 cycle의 개수가 정답 개수일까?
아니다.
cycle이 $2$개 초과여도 무조건 $2$번으로 정답을 낼 수 있다.
그냥 모든 싸이클을 연결시킨다고 생각해본다. 각 싸이클에서 $1$개 빼고 모두 제자리를 찾아가게 된다.
싸이클의 개수만큼 제자리가 맞지 않는 원소들이 생기며 이것들을 다시 한 번의 연산으로 풀어줄 수 있다.
permutation cycle문제들은 기본적인거 말고는 구현이 좀 헷갈리는것같다.
Comments