백준 1248 : 맞춰봐

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

1248번: 맞춰봐

[ 문제풀이 ]

백트래킹 기반의 완전 탐색으로 해결할 수 있는 문제이다.

처음에는 중복 숫자가 허용되지 않는다는 조건이 없어서 21^10의 경우의 수가 존재하니 완전 탐색으로 불가능하다고 생각하였다.

그런데 아무리 고민해봐도 완전 탐색이 아니고서는 해결할 수 없을 것 같아서 가능성 없는 경우들을 걸러내어 최대한 경우의 수를 줄여나가도록 구현하니깐 통과하였다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	static int N;
	static char[][] map;
	static int[] nums;
	static boolean find;

	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			N = Integer.parseInt(br.readLine());
			String input = br.readLine();
			map = new char[N][N];
			nums = new int[N];
			int pos = 0;
			for (int i = 0; i < N; ++i) {
				for (int j = i; j < N; ++j) {
					map[i][j] = input.charAt(pos++);
				}
			}
			dfs(0);
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	public static void dfs(int depth) {
		if (find) return;
		if (depth == N) {
			for (int i = 0; i < N; ++i) {
				System.out.print(nums[i] + " ");
			}
			find = true;
			return;
		}

		if (map[depth][depth] == '+') {
			for (int i = 1; i <= 10; ++i) {
				nums[depth] = i;
				if (isVaild(depth) && !find) dfs(depth + 1);
			}
		} else if (map[depth][depth] == '-') {
			for (int i = -1; i >= -10; --i) {
				nums[depth] = i;
				if (isVaild(depth) && !find) dfs(depth + 1);
			}
		} else {
			nums[depth] = 0;
			if (isVaild(depth) && !find) dfs(depth + 1);
		}
	}

	public static boolean isVaild(int depth) {
		for (int i = 0; i <= depth; ++i) {
			int sum = 0;
			for (int j = i; j <= depth; ++j) {
				sum += nums[j];
				if (map[i][j] == '0' && sum != 0) return false;
				if (map[i][j] == '+' && sum <= 0) return false;
				if (map[i][j] == '-' && sum >= 0) return false;
			}
		}
		return true;
	}
}