[BOJ 1248] 맞춰봐 (Java)

BOJ 1248 맞춰봐

문제풀이

S[idx][idx]의 부호가 A[idx]의 부호를 나타낸다는 것을 바탕으로 각 자리의 부호를 만족하는 모든 경우의 수를 구하고 그 안에서 S의 모든 조건을 체크하는 함수를 통해 확인하는 방식을 생각하였으나 당연히 시간초과였다.

수열을 만든 후에 조건을 체크할 것이 아니라 조건에 맞는 수를 자리에 위치시켜야하고 그를 위해서는 합계를 기억하고 있어야한다는 생각까지는 하였으나 도저히 구현할 수가 없었다...

그러던 중 검색을 통해 백트래킹을 이용한 코드를 발견했다. 그래서 이 코드를 바탕으로 Java로 변환하면서 이해하였다. 다음에 다시 풀어봐야겠다...

• A 수열의 각 자리를 조건에 맞게 채워 나간다.
  - 각 자리에는 S[idx][idx]와 같은 부호만 올 수 있다.
  • 이전 까지의 합을 통해 해당 행의 조건을 모두 만족하는지 확인한다.

가장 중요한 부분은 이전 까지 구한 합계를 백트래킹 함수의 매개변수로 넘기는 것 이다.

구현코드

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

public class B1248_맞춰봐 {
	static int[] A;
	static char[][] S;
	static int N;

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

		A = new int[N];
		S = new char[N][N];

		char[] line = br.readLine().toCharArray();
		int limit = N * (N + 1) / 2;
		int r = 0, c = 0;
		for (int i = 0; i < limit; ++i) {
			S[r][c] = line[i];
			c++;
			if(c == N) {
				r++;
				c = r;
			}
		}

		// A를 뒤쪽에서부터 채워나간다. 
		backtracking(N - 1, 0);
	}
	
	// boolean형의 리턴을 통해 찾는 즉시 backtracking이 끝나도록 한다. 
	private static boolean backtracking(int depth, int sum) {
		// N개의 숫자를 모두 정했을 때 탈출 
		if(depth == - 1) {
			for (int i = 0; i < N; ++i) {
				System.out.print(A[i] + " ");
			}
			return true;
		}
	
		// 현재 depth에 넣을 숫자를 찾는다. 
		for(int i = -10 ; i <= 10 ; ++i) {
			// 현재 depth에서 선택할 수 있는 부호를 S[depth][depth]에서 확인한다. 
			if((S[depth][depth] == '+' && i <= 0) ||
			   (S[depth][depth] == '-' && i >= 0) ||
			   (S[depth][depth] == '0' && i != 0)) continue;
			
			// 합계를 구하여 S[depth][i]의 조건을 만족하는지 확인한다.
			boolean flag = true;
			int tempSum = sum + i;
			
			// 이전에 구한 S[depth][N - 1] ~ S[depth][depth + 1]의 합계 조건을 확인한다.
			for(int j = N - 1 ; j >= depth + 1 ; --j) {
				if((S[depth][j] == '+' && tempSum <= 0) ||
				   (S[depth][j] == '-' && tempSum >= 0) ||
				   (S[depth][j] == '0' && tempSum != 0)) {
					flag = false;
					break;
				}
				// 이전에 선택되어있던 숫자를 빼가면서 확인한다. 
				tempSum -= A[j];
			}
			
			if(flag) {
				A[depth] = i;
				if(backtracking(depth - 1, sum + i)) return true;
			}
		}
		return false;
	}
}