[백준] 1248. Guess (Java)

문제

1248번: Guess

 

 

알고리즘

완전탐색, 백트래킹

 

 

풀이

한 자리에 -10 ~ 10 까지 21개의 수가 올 수 있고, n이 최대 10이므로 

만들 수 있는 경우의 수는 최대 21^10 으로 굉장히 커진다.

 

하지만 matrix의 (i, i) 칸을 통해 i 자리 수의 부호를 알 수 있어 경우의 수를 줄일 수 있고, 백트래킹을 통해 시간을 단축할 수 있다.

 

 

주어진 matrix를 2차원 배열에 저장하고 (board[n][n])

현재 수열을 1차원 배열에 저장하고 (num[n + 1])

현재 수열의 누적합을 1차원 배열에 저장한다. (sum[n + 1])

 

 

dfs 함수의 동작은 다음과 같다.

dfs(int count)      [count: 현재 숫자가 들어갈 인덱스]

 

1. 지금까지 만든 수열이 규칙에 맞지 않으면 반환한다.

2. 길이 n의 수열을 만들었다면 해당 수열을 출력하고 프로그램을 종료한다.

3. matrix의 (count, count) 칸을 보고 숫자의 부호에 맞게 숫자를 수열에 추가한 후 dfs(count + 1)을 호출한다.

 

---

수열에 원소 추가

 

수열의 (count)번째에 board[count][count]의 부호와 동일한 숫자를 추가해야하므로

 

1. board[count][count] 가 0 이라면

num[count] 에 0을 저장하고, sum[count]에 sum[count - 1] + 0 을 저장하고 dfs(count + 1)를 호출한다.

 

2. board[count][count] 가 1 혹은 -1 이라면

부호에 따라 1 ~ 10  혹은 -1 ~ -10 까지 num[count]에 i 를 저장, sum[count - 1] + i 를 저장, dfs(count + 1) 호출을 반복한다.

 

---

수열이 규칙에 맞는 지 확인

 

수열에 숫자가 추가될 때마다 수열의 유효성을 검사하기 때문에

새로 추가된 숫자에 대해서만 유효성을 검사하면 된다.

 

따라서 만약 i번째 숫자를 추가했다면

matrix의 [1][i] 부터 matrix의 [i - 1][i] 의 규칙만 맞는지 확인하면 된다. (matrix[i][i]에 해당하는 원소를 추가했으므로 검사 불필요)

 

예를 들어 i가 4라면

num[1] 부터 num[4] 까지 합의 부호가 matrix[1][4] 와 일치하고

num[2] 부터 num[4] 까지 합의 부호가 matrix[2][4] 와 일치하고

num[3] 부터 num[4] 까지 합의 부호가 matrix[3][4] 와 일치한다면 유효한 수열이다.

 

이때 합을 한 번에 계산하기 위해서 누적합을 sum에 저장하였다.

a부터 b까지 원소의 합을 sum[b] - sum[a - 1] 을 수행하여 한 번에 구할 수 있다.

 

 

코드

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

public class Main {
	static int N, board[][], num[], sum[];

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		board = new int[N + 1][N + 1];
		num = new int[N + 1];
		sum = new int[N + 1];

		String str = br.readLine();
		int index = 0;
		for (int i = 1; i <= N; i++) {
			for (int j = i; j <= N; j++) {
				char c = str.charAt(index++);

				if (c == '0') board[i][j] = 0;
				else if (c == '+') board[i][j] = 1;
				else if (c == '-') board[i][j] = -1;
			}
		}

		dfs(1);
	}

	static void dfs(int count) {

		if (!check(count - 1)) return;

		if (count > N) {
			StringBuilder sb = new StringBuilder();
			for (int i = 1; i < count; i++)
				sb.append(num[i]).append(" ");

			System.out.println(sb);
			System.exit(0);
		}

		int sign = board[count][count];

		if(sign == 0) {
			num[count] = 0;
			sum[count] = sum[count - 1] + 0;
			dfs(count + 1);
		}
		else {
			for (int i = 1; i <= 10; i++) {
				num[count] = sign * i;
				sum[count] = sum[count - 1] + sign * i ;
				dfs(count + 1);
			}
		}
		
	}

	private static boolean check(int count) {

		for (int i = 1; i < count; i++)
			if (Integer.signum(sum[count] - sum[i - 1]) != board[i][count])
				return false;
		return true;
	}
}