본문 바로가기

알고리즘 관련/BOJ

BOJ)14936 엘리베이터 장난

문제: icpc.me/14936


엘리베이터에서 m초 동안 4가지 동작을 수행할 수 있는데, m초가 지났을 때 버튼의 모습의 경우의 수를 세는 문제이다.

n,m제한이 상당히 크고, 경우의 수를 구하는 문제이므로 어렵게 접근할 수 있으나, 이는 함정이고

어짜피 같은 동작을 두 번 수행할 경우 원점으로 돌아가게 되기 때문에 모든 경우를 생각해볼 수 있다.

모든 경우의 수는 결국 x번 버튼을 누르는 경우의 퍼뮤테이션 이기에

4P0+4P1+4P2+4P3+4P4개 밖에 되지 않는다. 따라서 저 모든 경우에 대하여 직접 버튼을 뒤집어주어도 충분히 시간 내에 동작 할 수 있다.

9
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
int n, m, a[4];
vector<int> vt;
set<vector<int>> st;
vector<int> t;
int func(vector<int> &v, int rem, int flag) {
    if (rem == 0)return rem;
    if (flag == 1) {
        for (int i = 0; i < v.size(); i++) {
            v[i] ^= 1;
            rem--;
        }
    }
    else if (flag == 2) {
        for (int i = 0; i < v.size(); i += 2) {
            v[i] ^= 1;
            rem--;
        }
    }
    else if (flag == 3) {
        for (int i = 1; i < v.size(); i += 2) {
            v[i] ^= 1;
            rem--;
        }
    }
    else {
        for (int i = 0; i < v.size(); i += 3) {
            v[i] ^= 1;
            rem--;
        }
    }
    return rem;
}
int main() {
    scanf("%d%d"&n, &m);
    vt.assign(n, 0);
    for (int i = 0; i < 4; i++)
        a[i] = i + 1;
    st.insert(vt);
    do {
        int curr = m;
        t.assign(n, 0);
        for (int i = 0; i < 4; i++) {
            curr = func(t, curr, a[i]);
            if (curr >= 0)
                st.insert(t);
            else
                break;
        }
    } while (next_permutation(a, a + 4));
    printf("%d\n", st.size());
    return 0;
}
cs



'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)14939 불 끄기  (0) 2017.12.04
BOJ)14938 서강그라운드  (0) 2017.12.04
BOJ)11670 초등 수학  (0) 2017.11.15
BOJ)3136 평면도  (0) 2017.11.15
BOJ)14195 DotB  (0) 2017.11.15