https://www.acmicpc.net/problem/1091
문제 요약
- 길이 48인 카드 나열이 있음
- 카드는 가장 앞에서부터 0, 1, 2, 0, 1, 2, ... 플레이어에게 줄 것임
- 카드를 섞는 규칙이 있음 (1 : 1 대응 같은 shuffle)
- 각 카드마다 특정한 플레이어에게 주고 싶은 조건이 있음
- 조건을 만족하는 최소 횟수 구하기
접근법
- 순환 주기가 있을 것임 : 돌고 돌아도 48장 안에서만 돌 것이므로
- 싸이클이 여러개 있을 것임
- 섞고 섞었을때 제자리로 오기까지 가장 오래걸릴때 대략 얼마가 걸릴까
- 여러가지 싸이클들의 순환주기의 최소공배수일 것임
- 최소 공배수를 크게 만들어 보기 위해서 각각 싸이클의 순환 주기가 2, 3, 5, 7, 11, 13, ....이라고 보면
- 2, 3, 5, 7, 11, 13 의 순환주기를 있는 싸이클이 있을때의 길이가 41임
- 이때의 최소공배수가 30030
- 더 빡빡하게 만들면 8, 3, 5, 7, 11, 13 일때 길이가 47, 최소공배수는 120120
- 매번 비교한다고 해도 120120 * 48 = 5765760
- 완전탐색으로 해볼만함
newbieski