백준 23284 모든 스택 수열 c++ [컴공과고씨]

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

23284번: 모든 스택 수열

문제를 보고 일단 구해보려고 직접 써보았다.

그러다 보니 떠오른생각이 N-Queen하고 비슷한 문제인 것을 느껴서 백트래킹 쪽으로 생각하게 되었다.

왜 비슷하면 각 자리마다 숫자를 넣을 때 이 숫자를 넣으면 수열이 가능한지 아닌지를 판단 한 후 아니면 다른 수를 넣는식으로 가기 때문에 n-queen도 각 자리에 퀸이 들어갈지 아닐지를 판단하는 문제였어서 비슷하다고 느꼈다.

이런식으로 하나를 넣고 그 다음 수를 볼 때 들어갈 수 있는 수를 체크하고 들어갈 수 있으면 넣고 다음꺼가 가능한지 보는 형식으로 백트래킹 기법을 사용해야겠다는 생각이 들었다.

 

이제 수열이 안만들어지는 경우를 생각해보자

첫번째 수가 중복되면 안된다. 앞에 수에서 1과2가 나왔다면 그 다음 수는 1,2는 될 수 없다.

두번째 스택에 수를 순서대로 넣기 때문에 그 전보다 큰 수를 넣을 때는 이제까지 제일 큰 수 +1 보다 같거나 커야한다.

이게 헷갈리는데 설명을 하면

(next는 push할 다음 수)

이러한 각 자리에 수가 들어가서 수열이 가능한 경우 그 위치의 수가 next보다 작으면 next는 그대로 유지 해주고 만약 크거나 같다면 next에 +1을 해주어야한다.

 

이해가 안간다면 코드에 자세한 주석을 달아놨기 때문에 코드를 보며 이해하는것도 빠를 수 있다.

 

전체코드

#include <iostream>
using namespace std;
int n;
int num[11];
 
void function(int cnt, int next){
    if(cnt == n){ // 자리가 다 채워진 수열이면 옳바른 수열
        for (int i = 0; i < n;i++){
            cout << num[i] << " "; // 출력해줌
        }
        cout << '\n';
    }else{
        for (int i = 1; i <= n;i++){
            bool can = true; // 중복인지 아닌지 구별
            num[cnt] = i; // 현재 자리에 수를 정해줌
            for (int j = 0; j < cnt;j++){
                if(num[j] == num[cnt]){ // 중복확인
                    can = false;
                }
            }
            if(can){
                if(num[cnt - 1] < num[cnt] && num[cnt] < next){
                    //직전 수 보다 현재 들어온 수가 크고
                    //다음 넣을 수 보다 현재 들어온 수가 작다면
                    // 잘못된 수열 이므로 
                    break; // 더 이상 진행 x
                }
            }
            if(can){ // 옳바른 수열이라면
                if(next <= num[cnt]){ 
                    //현재 들어온 수가 새로운 수라면 next에 +1 해주어야함
                    function(cnt + 1, num[cnt]+1);
                }else{
                    //현재 들어 온 수가 이미 들어온 수를 꺼낸 것이라면
                    //next는 유지
                    function(cnt + 1, next);
                }
            }      
        }
    }
}
 
int main(){  
    cin >> n;
    function(0, 0);
    return 0;
}

체감 난이도	걸린시간	참고	사용 알고리즘
중	34min	x	백트래킹(back tracking)