[BOJ] 1248. 맞춰봐

이문제는 순열을 사용하여 접근하는 문제이다.

처음엔 간단히 단순 순열로 접근하여 푸는 문제 인지 알았다. 하지만 최악의 경우 21P10을 가지게 되므로 가지치가 상당히 중요한 문제로 생각하였다. 일단 문제를 쉽게 접근하기 위해 -,+,0으로 주어진 문자열을 2차원 배열의 형태로 만들어주었다. 행을 0부터 N까지로 잡고, 열을 현재행부터 N까지로 주어서 삼각형모양의 2차원배열을 만들었다. 그 후 순열로 접근하였다. 일단 순열을 0부터 N-1까지 정해줄때 해당 index는 2차원배열의 행과열이 같을때의 index의 부호와 같기때문에 크게 경우의 수를 줄일 수 있었고, 그 후 check라는 함수를 만들어 2차원배열의 해당 열의 원소들을 체크해주는 식으로 가지치기를 하였다.

푸는데 상당히 오랜시간이 걸렸고, check라는 함수를 구상하는데 상당히 어려움이 있었다. 가지치기의 방법에 대해 다시한번 생각해볼만한 것 같다.

package online.practice;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main_bj_1248_맞춰봐 {
    static int N;
    static int[][] map;
    static int[] pick;
    
    static boolean find;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        String str=br.readLine();
        
        map=new int[N][N];
        
        int index=0;
        for(int i=0;i<N;i++) {
            for(int j=i;j<N;j++) {
                char ch=str.charAt(index++);
                if(ch=='-')
                    map[i][j]=-1;
                if(ch=='+')
                    map[i][j]=1;
            }
        }
        
        pick=new int[N];
        find=false;
        perm(0);
    
    }
    
    static void perm(int depth) {
        if(find==true)
            return;
    
        if(depth==N) {
            for(int i=0;i<N;i++)
                System.out.print(pick[i]+" ");
            System.out.println();
            find=true;
            return;
        }
        
        if(map[depth][depth]==0) {
            pick[depth]=0;
            if(check(depth)) {
                perm(depth+1);
            }
        }
        
        for(int i=1;i<=10;i++) {
            pick[depth]=i*map[depth][depth];
            if(check(depth)) {
                perm(depth+1);
            }
        }
    }
    
    static boolean check(int depth ) {
        
        int sum=0;
        for(int i=depth; i>=0 ; i--) {
            sum+=pick[i];
            if(map[i][depth]==0) {
                if(sum!=0)    return false;
            }else if(map[i][depth]<0) {
                if(sum>=0)    return false;
            }else if(map[i][depth]>0) {
                if(sum<=0)    return false;
            }
        }
            
        return true;
    }
    
}