백준 2487번 섞기 수열

문제 설명

이번 문제는 처음에 [A1,A2,A3, ... ,An]의 카드가 순서대로 있을 때, 주어진 수열대로 섞을 경우 처음 상태로 돌아오는 최소 섞기 횟수를 구하는 문제입니다.

 

문제 풀이

아이디어

각 자리가 움직이는 규칙

[A1, A2, A3, ... An] 카드를 문제에서 제시한 예시 수열 [A3, A2, A5, A6, A1, A4] 대로  섞는 경우 각 자리의 움직임을 살펴보도록 하겠습니다.

 

A1은 첫 섞기에서 A3으로 이동하고 두 번째 섞기에서 A5, 세 번째 섞기에서 A1으로 되돌아옵니다.

그러므로 A1의 섞기 수열의 궤적은 3입니다.

 

A2는 첫 섞기에서 A2로 이동합니다.

그러므로 A2의 섞기 수열의 궤적은 1입니다.

 

A3는 A1섞기 수열의 궤적 내에 포함되어 있으므로 섞기 수열의 궤적은 3입니다.

 

A4는 첫 섞기 수열에서 A6로 이동하고 두 번재 섞기 수열에서 A4로 되돌아옵니다.

그러므로 A4의 섞기 수열의 궤적은 2입니다.

A5는 A1,A3의 섞기 수열의 궤적 내에 포함되어 있으므로 섞기 수열의 궤적은 3입니다.

 

A6는 A4 섞기 수열의 궤적 내에 포함되어 있으므로 섞기 수열의 궤적은 2입니다.

 

전체 섞기 수열의 궤적 구하기

모든 자리수가 자신만의 섞기 수열의 궤적을 가지고 있으므로 모든 자리수가 제자리로 돌아올 경우를 구하려면, 각 자리수의 섞기 수열의 궤적의 최소공배수를 구해주면 됩니다.

 

 

풀이

각 자리수의 섞기 수열의 궤적

각 자리수의 섞기 수열의 궤적을 구할 경우, 이동한 위치에 해당하는 자리수도 지금 구하고 있는 자리수와 같은 섞기 수열의 궤적을 나타냅니다.

그러므로 해당 위치에 대한 섞기 수열의 궤적은 또 구할 필요가 없으므로, visited 배열을 선언한 뒤 이동할 때마다 visited[이동한 위치]= True로 바꿔주면, 시간을 단축할 수 있습니다.

 

최소 공배수

유클리드 호제법을 이용해 최대공약수를 구한 뒤, 최대공약수를 통해 최소 공배수를 구해주면 됩니다.

 

 

 

해결

이번 문제는 각 자리수마다 반복되는 규칙이 있다는 것을 파악하고, 그 규칙을 최소화해줄 수 있는 최소 공배수를 생각해내어 비교적 쉽게 풀 수 있었습니다.

 

문제 링크 : https://www.acmicpc.net/problem/2487

2487번: 섞기 수열

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/2487.py