실력키우기 섞기수열(C++)

2255 : 섞기 수열

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 495 회    시도횟수: 3547 회   

A1, A2, …, AN으로 표시된 N 개의 카드를 정해진 방법으로 섞고자 한다. 그 섞는 방법은 1에서 N까지의 숫자로 이루어진 수열로 표시된다. 이 수열을 섞기 수열이라 하자. 섞기는 현재 가지고 있는카드에서 섞기 수열의 각 숫자가 나타내는 위치에 있는 카드를 순서대로 뽑아서나열하는 것이다.

예를 들어, N = 6이고 섞기 수열이 [3, 2, 5, 6, 1, 4]라고 하자. 카드의 처음 상태가 [A1, A2, A3, A4, A5, A6]일 때, 섞기를 한 번 실행하면 카드의 순서가 다음과 같이 된다.

[A3, A2, A5, A6, A1, A4]

이 상태에서 다시 한 번 섞기를 실행하면 카드의 순서가 [A5, A2, A1, A4, A3, A6]이 되고, 다시 한 번 더 섞기를 실행하면 카드의 순서가 [A1, A2, A3, A6, A5, A4]가 된다. 이렇게 섞기를 반복하면 카드의 순서가 처음 상태인 [A1, A2, A3, A4, A5, A6]이 된다. 처음 상태로 돌아 올 때까지 반복한 섞기의 최소 횟수를 주어진 섞기 수열의 궤적이라 한다. 임의의 섞기 수열이 주어졌을 때, 그 섞기 수열의 궤적을 구하는 프로그램을 작성하시오.

 

첫 번째 줄에 카드의 수 N이 주어진다. N은 1 이상 20,000 이하의 수이다.
두 번째 줄에 섞기 수열을 나타내는 N 개의 자연수가 빈칸을 사이에 두고 주어진다.

첫 번째 줄에 입력으로 주어진 섞기 수열의 궤적을 출력한다. 단, 궤적이 1 이상 2,000,000,000 이하인 입력만 주어진다.

[Copy] 6 3 2 5 6 1 4

[Copy] 6

출처 : KOI 전국 2009 고1

/**************************************************************
    Problem: 2255
    User: a132034
    Language: C++
    Result: Success
    Time:9 ms
    Memory:1740 kb
****************************************************************/
 
 
#include    <iostream>
using namespace std;
 
int main()
{
    int N;
    int * arr;
    bool * visit;
 
    int count = 1;
    cin >> N;
    arr = new int[N];
    visit = new bool[N];
    for (int i = 0; i < N; ++i)
    {
        cin >> arr[i];
        visit[i] = false;
    }
    //end input area
 
    int tmpCount = 0;
    int tmp;
    for (int i = 0; i < N ; ++i)
    {
        //아직 방문하지 않은 점. 방문한 점은 싸이클이 되어 모두 같은 Count를 가진다.
        if (visit[i] == false)
        {
            tmpCount = 0;
            tmp = i + 1;
            while (true)
            {
                if (tmp == i + 1 && tmpCount != 0)
                    break;
 
                tmpCount++;
                visit[tmp - 1] = true;
                tmp = arr[tmp - 1];
            }
 
            int b = count > tmpCount ? count : tmpCount;
            int s = count < tmpCount ? count : tmpCount;
            if (b%s == 0)
            {
                count = b;
            }
            else
            {
                for (int z = 1;; ++z)
                {
                    int big = b * z;
                    if (big%s == 0)
                    {
                        count = big;
                        break;
                    }
                }
            }
        }
    }
 
 
    cout << count;
    return 0;
}

공식 자체는 그렇게 어렵지 않으나, 인풋이 큰 값이 들어올 수 있기 때문에 몇 가지 속도를 높일만한 알고리즘을 생각해내야 한다. 

이 코드의 핵심은..

1. 모든 자리는 궤적이 있고, 그 안에 있는 궤적에 있는 위치는 모두 자기 자신으로 오기 위해 섞는 횟수가 동일하다.

ex) 3 2 5 6 1 4 일 경우 첫 번째 자리는 3->5->1 세번만에 돌아오는 궤적을 따른다. 

이는 세 번째 자리도 동일 5-> 1-> 3

2. 각각 자기 자신으로 들어오기 위한 섞기 횟수가 다르므로 섞기 모든 횟수간의 최소공배수가 최소 횟수가 된다. 

이 두가지 기본 개념을 가지고 문제를 풀이했다. 

한 번 방문한 곳은 방문하지 않기 위해 visit배열을 사용하였다. 

최소공배수는 a b c가 있을 때 a b의 최소공배수가 d 일 경우 c d의 최소공배수가 결국 a b c의 최소공배수와 같으므로 루프를 돌며 최소공배수를 수정하는 방식으로 만들었다. 

나머지는 크게 어렵지 않았다. 시간을 더 줄일수도 있을 것 같으나.. 우선 푼 것에 만족.