[BOJ] 15684 사다리조작

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

15684번: 사다리 조작

오늘도 어김없이 문제를 제대로 읽지 않아 시간을 버렸다.

답이 3 초과인 경우를 배제해줬어야 했는데... 잘 읽어야겠다 ㅋㅋ

 

답이 3 초과인 경우를 배제해줬더니 시간초과가 떴다. 재귀를 돌 때 중복되는 경우가 발생하여 idx를 인자로 줘서 경우의 수를 줄여주었다.

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

int N,M,H,ans=INT_MAX;
int map_[30][10];

void input() {
    cin>>N>>M>>H;
    int a,b;
    for(int i=0;i<M;i++){
        cin>>a>>b;
        map_[a-1][b-1]=1; // 1은 오른쪽으로 갈 수 있다는 뜻
        map_[a-1][b]=-1; // -1은 왼쪽으로 갈 수 있다는 뜻
    }
}

void init(){
    
}


void check(int n){
    bool flag2=true;
    for(int i=0;i<N;i++){
        if(!flag2) break;
        int point=i,y=0;
        while(y!=H){
            if(map_[y][point]==1){ // 1이면 오른쪽으로 이동
                point++;
            }else if(map_[y][point]==-1){ // -1이면 왼쪽으로 이동
                point--;
            }
            y++; //사다리는 무조건 한번 내려가야 한다.
        }
        if(point!=i) flag2=false;
    }
    if(flag2) ans=min(ans,n);
}

void solution(int n,int idx){
    check(n);
    for(int i=idx;i<H;i++){
        for(int j=0;j<N-1;j++){
            if(map_[i][j]==0&&map_[i][j+1]==0){ // 세로선 중 한쪽이라도 가로선이 연결되어있으면 가로선을 사이에 놓을 수 없다.
                map_[i][j]=1;
                map_[i][j+1]=-1;
                if(n+1<=3) solution(n+1,i); //3이상일 경우 재귀를 돌지 않는다.
                map_[i][j]=0;
                map_[i][j+1]=0;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution(0,0);
    if(ans==INT_MAX) cout<<-1;
    else cout<<ans;
    return 0;
}