사다리 조작

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

15684번: 사다리 조작

삼성 S직군 역량평가 기출문제다.

일단 문제파악 순서는

사다리를 놓을수있고, 놓았을때 오른쪽으로갈수있는 부분을 1, 왼쪽으로 갈수있는 부분을 2로표시했고

사다리를 내려가서 확인하는 과정을 game()함수로 생성했으며 함수 안에서 i번째 자리가 , i 출구로 나오는지 확인하고

아닐시 다시 확인하는 방식으로 진행함

우선, 이문제는 배열의 크기가 커봐야 30 * 10 = 300 배열에 조합의크기가 300C3정도의 크기인데 이것보다 작기때문에

모든경우의수를 해봐도 괜찮을것같다는 생각으로 순열을 사용한 조합으로 문제를 풀었다.

#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
 
int n, m, h;
int map[32][11];
int temp[32][11];
vector<pair<int, int>>v;
vector<int> per;
int ans;
bool ending = false;
 
void game(vector<int>&a, int cnt){        
    do {
        bool ongame = true;
        for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= n; j++) {
                temp[i][j] = map[i][j];
            }
        }
        for (int i = 0; i < a.size(); i++) {
            if (a[i] == 1) {
                if (temp[v[i].first][v[i].second] == 0 && 
                    temp[v[i].first][v[i].second + 1]== 0 &&
                    v[i].second + 1 <= n) {
                    
                    temp[v[i].first][v[i].second] = 1;
                    temp[v[i].first][v[i].second + 1] = 2;
                    
                }
                else {
                    ongame = false;
                }
            }
        }
        
        if (ongame) {
            int cox = 0;
            for (int i = 1; i <= n; i++) {
                int x = 1; int y = i; int idx = i;
                bool endloop = false;
                while (!endloop) {
                    if (temp[x][y] == 0) {
                        x++;
                    }
                    else if (temp[x][y] == 1) {
                        y++;
                        x++;
                    }
                    else if (temp[x][y] == 2) {
                        y--;
                        x++;
                    }
 
                    if (x == h + 1) {
                        if (y == idx) {
                            cox++;
                        }
                        else {
                            i = n + 1;
                        }
                        endloop = true;
                    }
                }
            }
            if (cox == n) {
                ending = true;
            }
        }
    } while (prev_permutation(a.begin(), a.end()));
 
}
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> m >> h;
    for (int i = 0; i < m; i++) {
        int H, N;
        cin >> H >> N;
        map[H][N] = 1;
        map[H][N + 1] = 2;
    }
    
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j < n; j++) {
            if (map[i][j] == 0) {
                v.push_back({ i,j });
            }
        }
    }
    vector<int> per[4];
    for (int i = 0; i < v.size(); i++) {
        if (i < 1) {
            per[1].push_back(1);
        }
        else per[1].push_back(0);
        if (i < 2)
            per[2].push_back(1);
        else
            per[2].push_back(0);
        if (i < 3)
            per[3].push_back(1);
        else
            per[3].push_back(0);
        per[0].push_back(0);
    }
    
    for (int i = 0; i < 4; i++) {
        game(per[i], i);
        if (ending == true) { cout << i << '\n'; return 0; }
    }
    cout << -1 << '\n';
    return 0;
 
}

코드는 다음과같으며 채점결과를보니 1290ms정도 나왔는데 가로 배열이 한두줄만 더길었어도 실패했을것같다

 

순열조합 사용하는 방식은 조금 지양하고 재귀 쓰는것에 익숙해지자.