[백준] 3967 - 매직스타

[문제링크]

3967번: 매직 스타

 

0. 12개의 숫자로 육각성을 완성했을때, 모든 변의 합이 26으로 같아야 한다

 

1. brute-force로 진행시 12! = 479001600의 가짓수

• 1초 시간제한 내 풀이 불가능

2. 모든 변을 완성시키지 말고, 완성되는대로 검사한다

• 위-왼쪽부터 차례대로 채워나갈 경우, 5개의 숫자를 선택하면 윗 변 하나가 완성된다
• 해당 변의 합이 26일 경우에만 진행

3. 사전순으로 가장 앞서는 결과를 출력해야하므로, 작은 수부터 큰 수로 진행하며 하나라도 성공하면 종료, 반환한다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb;


        num = new int[12];
        isUsed = new boolean[12]; 
        int idx=0;

        String[] input = new String[5];

        for (int i = 0; i < 5; i++) {

            input[i] = br.readLine();

            for (int j = 0; j < input[i].length(); j++) {
                if(input[i].charAt(j)=='x')num[idx++]=0;
                else if(input[i].charAt(j)!='.') {
                    num[idx]= input[i].charAt(j)-'A'+1;
                    isUsed[num[idx++]-1]=true;
                }
            }
        }

        String s = rec(0);
        idx=0;
        for (int i = 0; i < 5; i++) {
            sb=new StringBuilder(input[i]);

            for (int j = 0; j < sb.length(); j++) {
                if(sb.charAt(j)!='.') {
                    sb=sb.replace(j, j+1, ""+s.charAt(idx++));
                }
            }
            System.out.println(sb);
        }

    }

    static boolean[] isUsed;
    static int[] num;

    static String rec(int idx) {
        String s="";

        if(idx==5) {
            if(num[1]+num[2]+num[3]+num[4] != 26)return null;
        }
        else if(idx==8) {
            if(num[0]+num[2]+num[5]+num[7] != 26)return null;
        }
        else if(idx==11) {
            if(num[0]+num[3]+num[6]+num[10] != 26)return null;
            if(num[7]+num[8]+num[9]+num[10] != 26)return null;
        }
        else if(idx==12) {
            if(num[1]+num[5]+num[8]+num[11] != 26)return null;
            if(num[4]+num[6]+num[9]+num[11] != 26)return null;
            for (int i = 0; i < num.length; i++) {
                s+=(char)(num[i]+'A'-1);
            }
            return s;
        }

        if(num[idx]!=0) {
            return rec(idx+1);//이미 초기에 숫자가 있었다면 
        }
        else {
            for (int i = 0; i < 12; i++) {
                if(!isUsed[i]) {
                    //사용한적 없으면
                    num[idx]=i+1;
                    isUsed[i]=true;

                    if( (s = rec(idx+1)) != null ) {
                        return s;
                    }

                    num[idx]=0;
                    isUsed[i]=false;
                }
            }
        }
        return null;
    }

    static int pint(String s) {
        return Integer.parseInt(s);
    }

}

결과 화면