[랜덤] BOJ 1091 - 카드 섞기

https://www.acmicpc.net/problem/1091

 

아이디어: 10분

코딩: 15분 

접근법

카드를 석는 방법대로 카드의 위치를 옮기는 것이 핵심인 문제이다.

이는 직접 과정을 하나하나 하다보면 점화식을 구할 수 있다.

 

먼저 현재 카드를 before={0, 1, 2, 0, 1, 2}이고, 섞는 순서를 S={1 4 0 3 2 5}라고 가정해보자. 그리고 섞은 후의 배열을 after[]라고 하자. S를 0번부터 ~5번까지 돌면서 각 상황을 보자.

 

 

before의 S[0]번째 카드는 after의 0번으로 이동해야한다.

이를 식으로 표현하면 after[0] = before[S[0]]

 

before의 S[1]번째 카드는 after의 1번으로 이동해야한다.

이를 식으로 표현하면 after[1] = before[S[1]]

 

따라서, 섞는 순서를 반복문으로 표시하면 다음과 같이 표현할 수 있다.

for(int i=0;i<n;i++) {
     after[i] = before[s[i]];
}

 

시간 복잡도

문제의 경우, 카드가 48장 밖에 되지 않고 시간도 2초이므로 브루트포스로 풀어도 시간초과가 나지 않는다.

P가 될때까지 섞는 시간: O(N)

섞는 시간: O(N)

P가 되었는지 확인하는 시간: O(N)

총 O(N^3)에 문제를 해결할 수 있다.

 

코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>

#define ll long long

using namespace std;

int n;
int p[49];
int s[49];
int before[49];
int after[49];

bool check() {
    for(int i=0;i<n;i++) {
        if(before[i] != p[i])
            return false;
    }
    return true;
}

void init() {
    for(int i=0;i<n;i+=3) {
        for(int j=0;j<3;j++) {
            before[i+j] = j;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;
    for(int i=0;i<n;i++) {
        cin >> p[i];
    }
    for(int i=0;i<n;i++) {
        cin >> s[i];
    }

    init();

    int res = -1;
    for(int cnt =0;cnt<=1e7;cnt++) {
        if(check()) {
            res = cnt;
            break;
        }

        for(int i=0;i<n;i++) {
             after[i] = before[s[i]];
        }
        for(int i=0;i<n;i++) {
            before[i] = after[i];
        }
    }

    cout<<res;

    return 0;
}