4583. 세븐 카드 섞기 게임

4583. 세븐 카드 섞기 게임

문제 자체가 쉬워보였지만, K값이 10^12 이기 때문에 시간을 단축하는게 아주 중요한 문제라고 생각했다.

그래서 어떤 규칙이 있을까 생각해보다가, 단순하게 따로 수학적인 규칙이나 증명이 있을 수 없을 것 같다고 생각을 했다.

그렇다면 문제의 조건에서 풀기 위해서는 반드시 맨 처음의 값이 카드를 섞으면서 다시 중복해서 나와야한다고 생각했다. 그래야지 그때를 

기준으로 K값을 나머지 연산으로 줄여 풀 수 있기 때문이었다.

그래서 while 문을 통해서 맨 첫번째 0123456 이 아닌, 그 다음 0123456 이 존재하는지 여부를 확인하고 그 때의 값을 m2에 저장하였다. 

그리고 while 문을 빠져나오면 K를 m2 로 나눈 나머지 값으로 변경시켜준다. 

그리고 위의 while 문을 동일하게 수행하되 K 를 감소하면서 0이 될때까지 수행하면 결과를 얻을 수 있다.

단 조심할 점은 K 를 int 형으로 처음에 선언해서 런타임에러가 발생했다는 점!

<정답 코드>

#include<iostream>
 
using namespace std;
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        int num[8] = { 0,0,1,2,3,4,5,6 };
        int op[20][2];
        int M;
        long long K;
        cin >> M >> K;
        
        for (int i = 0; i < M; i++)
            cin >> op[i][0] >> op[i][1];
 
 
        int m = 0;
        long long m2 = 0;
        while (true)
        {
            if (m == M)
                m = 0;
 
            if (m2 != 0 && m == 0 && num[1] == 0 && num[2] == 1 && num[3] == 2 && num[4] == 3 && num[5] == 4 && num[6] == 5)
                break;
            
 
            int tmp = num[op[m][0]];
            num[op[m][0]] = num[op[m][1]];
            num[op[m][1]] = tmp;
 
            m++;
            m2++;
        }
 
        K = K % m2;
        m = 0;
 
        while (K--)
        {
            if (m == M)
                m = 0;
 
 
            int tmp = num[op[m][0]];
            num[op[m][0]] = num[op[m][1]];
            num[op[m][1]] = tmp;
 
            m++;
        }
 
        cout << "#" << t << " ";
        for (int i = 1; i <= 7; i++)
            cout << num[i];
 
        cout << endl;
 
    }
 
    return 0;
}