글 읽기 - next_permutation과 dfs의 차이

shinyou1024 4년 전 0

이 문제를 next_permutation으로 구현하면 통과하고 DFS로 순열을 직접 구현하면 시간초과가 나네요.

꼭 next_permutation을 써야만 하는지 궁금해서 검색해보니까 DFS로도 통과하신 분들이 있는데

제가 짠 DFS로는 통과하지 못하는 이유가 뭔지 잘 모르겠습니다 ㅠㅠ

#include <iostream>
using namespace std;
int n;
int result[55][15];
int sel[10];
int visit[10];
int ans = 0;
void simul() {
    int score=0;
    int idx = 0;
    for(int inning=0; inning<n; inning++) {
        int base[3] = {0, 0, 0};
        int out = 0;
        while(out<3) {
            int player = sel[idx];
            int now = result[inning][player];
            if(now==0) {
                out++;
            }
            else {
                // 원래 주자 옮기기
                for(int i=2; i>=0; i--) {
                    if(base[i]==1) {
                        if(now+i>=3) {
                            score+=1;
                            base[i] = 0;
                        }
                        else {
                            base[now+i] = 1;
                            base[i] = 0;
                        }
                    }
                }
                if(now!=4) {
                    base[now-1] = 1;
                }
                else {
                    score+=1;
                }
            }
            idx = (idx+1)%9;
        }
    }
    if(score>ans) ans = score;
}

void permu(int depth) {
    if(depth==9) {
        simul();
        return;
    }
    for(int i=2; i<=9; i++) {
        if(depth==3) {
            sel[depth] = 1;
            permu(depth+1);
            continue;
        }
        if(visit[i]) continue;
        visit[i] = 1;
        sel[depth] = i;
        permu(depth+1);
        visit[i] = 0;
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i=0; i<n; i++) {
        for(int j=1; j<=9; j++) {
            cin >> result[i][j];
        }
    }
    permu(0);
    cout<<ans;
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

next_permutation과 dfs의 차이

shinyou1024 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말