[백준/Java] 3967: 매직스타

문제: https://www.acmicpc.net/problem/3967

 

 

 

 

 

조건

• TimeLimit = 2s
• 1<= N <=20, |S| <=100만
• 크기가 1 이상의 부분수열 중, 합이 S가 되어야 함

 

풀이

• 완전탐색
  • 최대 12개의 순열을 나열해야한다. O(12!)이므로 약 4억이라 불가능..
  • 하지만 가지치기를 잘 해보면 가능할지도? (1억과 크게 차이가 안나니까)
  • 순열이므로 visited를 통해 중복 관리를 해주자
  • 12개의 숫자를 모두 다 사용했을 때를 trigger로 한다
  • 이때 모든 라인에 대해, 각 라인의 합이 26이어야한다
  • 필요한 숫자들을 new int[12] 배열로 가정했을 때, 각 라인에 해당하는 index는 다음과 같다
    • line 1 -> 0, 2, 5, 7
    • line 2 -> 1, 2, 3, 4
    • line 3 -> 0, 3, 6, 10
    • line 4 -> 7, 8, 9, 10
    • line 5 -> 1, 5, 8, 11
    • line 6 -> 4, 6, 9, 11

 

코드

import java.io.*;
import java.util.*;

public class Main {

	static boolean[] visited = new boolean[12];
	static int[] select = new int[12];
	static String ans;

	static Set<Integer> line1 = Set.of(0, 2, 5, 7);
	static Set<Integer> line2 = Set.of(1, 2, 3, 4);
	static Set<Integer> line3 = Set.of(0, 3, 6, 10);
	static Set<Integer> line4 = Set.of(7, 8, 9, 10);
	static Set<Integer> line5 = Set.of(1, 5, 8, 11);
	static Set<Integer> line6 = Set.of(4, 6, 9, 11);
	static Set<Integer>[] lines = new Set[] { line1, line2, line3, line4, line5, line6 };

	static int[] loc = { 4, 10, 12, 14, 16, 20, 24, 28, 30, 32, 34, 40 };

	public static void main(String[] args) throws IOException {

		// input
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

			char[] row = br.readLine().toCharArray();

			for (int j=0; j<9; j++) {

				int idx = 9*i + j;

				if (size < 12 && idx == loc[size]) {
					
					if (row[j] >= 65 && row[j] <= 76) {
						select[size] = row[j];
						visited[row[j]-65] = true;
					}
					
					else {
						select[size] = -1;
					}

					size ++;
				}
			}
		}

		// dfs
		dfs(0);

		// result
		StringBuilder sb = new StringBuilder();
		size = 0;
		for (int i=0; i<5; i++) {
			for (int j=0; j<9; j++) {

				int idx = 9*i + j;
				if (size < 12 && idx == loc[size]) {
					sb.append(ans.charAt(size));
					size++;
				}
				
				else sb.append(".");

			}

			sb.append("\n");
		}

		System.out.print(sb);
	}






	static void dfs(int size) {

		if (ans != null) return;

		if (size == 12) {

			if (!validateAll()) return;

			StringBuilder sb = new StringBuilder();
			for (int i=0; i<12; i++) sb.append((char) (select[i]));
			ans = sb.toString();

			return;
		}

		if (select[size] != -1) {
			dfs(size+1);
			return;
		}

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

			if (visited[i]) continue;
			visited[i] = true;
			select[size] = i+65;
			dfs(size+1);
			visited[i] = false;
			select[size] = -1;

		}
	}

	
	

	static boolean validateAll() {
		
		for (Set<Integer> line : lines) {
			
			int sum = 0;
			for (int idx : line) {
				
				if (select[idx] == -1) return false;
				sum += select[idx];
				
			}
			
			if (sum != 64*4 + 26) return false;
		}
		
		return true;
	}

}