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; } Colored by Color Scripter

cs