[백준 / BOJ] 1091 카드 섞기

문제

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

1091번: 카드 섞기

N장의 카드를 3명의 플레이어에게 나눠줄려고 한다.

카드를 주어진 조건 S를 이용해 섞어서 P에 맞게 나눠줄 수 있는지 구하는 문제이다.

---

풀이 

지문이 난해한 문제다.

지문만 이해한다면, 시뮬레이션으로 풀면 되는데, 이때 최댓값을 계산 해줘야 한다.

이렇게 하면 안되지만... 나는 최댓값 계산에 실패해서 백준 채점 시스템을 이용해서 가지를 쳐가며 풀었다.

따라서, 증명이 보고싶다면 다른 블로그를 참조하는게 좋을거 같다.

 

카드의 갯수가 48 일때, 반복횟수는 다음과 같다.

 

A - 모든 카드가 P에 해당하는지 체크하는 과정 = 48 번
B - 카드를 섞는 과정 = 48번 (구현에 따라 48*2번이 될수도 있음)

C - B를 반복할 횟수 = K

따라서, 반복횟수 = A * B * K = 110592 * K

 

이때, K 의 값을 계산하는게 관건이다.

문제에서 주어진 시간제한이 2초이므로, 2억번 정도 반복이 가능하다고 가정했을때, K는 100000보다 조금 더 낮게 나온다.

 

K를 100000으로 가정하고 제출을 하면 AC가 나온다.

void solve(int cycle){
    if(valid()){
        ans = cycle;
        return;
    }
    if(cycle > N*100000) {
        ans = -1;
        return;
    }
    move();
    solve(cycle+1);
}

하지만 264 ms 가 걸렸고, 조금 더 줄일수 있을거 같다.

여차저차 줄여본 결과, K가 2550 일때, 8ms를 얻을 수 있었다.

void solve(int cycle){
    if(valid()){
        ans = cycle;
        return;
    }
    if(cycle > N*2550) {
        ans = -1;
        return;
    }
    move();
    solve(cycle+1);
}

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/1091%20카드%20섞기/main.cpp

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃