[백준 1248] 맞춰바 -Java

예제를 보면 -10 ~ 10 까지의 수 중 4개를 뽑아서
A[i]부터 A[j]까지 합이 0보다 크면 +, 0이면 0, 0보다 작으면 -이다. 여기서 i는 항상 j보다 작거나 같다.
조건을 만족시켜야 한다

즉, 2차원배열을 map이라할때 map[i][j]가 있고, 다음 과 같은 식으로 나타낼 수 있다

예제출력 1
(0,0) = -2	(1,1) = 5	(2,2) = -3	(3,3) = 1
(0,1) = 5-2	(1,2) = 5-3	(2,3) = -3+1
(0,2) = 5-2-3	(1,3) = 5-3+1
(0,3) = 5-2-3+1

이처럼 (0,0) ~ (3,3) 까지 "-+0++++--+" 를 만족하는 숫자를 찾아 리턴하면 된다.
(문제에 나와있듯 답이 여러가지일 경우 아무거나 출력하면 된다.)

조건의 만족하는 숫자를 찾기 위해 길이가 N인 배열에서 -10 ~ 10까지 숫자들을 각각 대입하여
DFS를 이용하여 구한다.

아래의 코드로 구현하였다.

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

 
public class Main {

	static int n, sum;
	static String arr;
	static int[] result;
	static Character[][] map;

	static void dfs(int idx) {
    	// 조건이 모두 성립되면 시스템종료
		if (idx == n) {
			String str = "";
			for(int i = 0; i < result.length; i++) {
				str += result[i] + " ";
			}
			System.out.print(str);

			// 시스템을 종료.
			System.exit(0);
		}
		
        // -10~10 까지 수를 비교
		for(int i = -10; i < 11; i++) {
			result[idx] = i;
            // 조건이 만족할 경우 true
			if(cheak(idx+1)) {
				dfs(idx+1);
			}
		}

	}
	
	static boolean cheak(int length) {
    	// 조건이 만족하는지 확인 
		for(int i = 0; i < length; i++) {
			int sum = 0;
			for(int j = i; j < length; j++) {
				sum += result[j];
				if(map[i][j] != (sum == 0 ? '0' : (sum > 0) ? '+' : '-')) {
					return false;
				}
			}
		}

		return true;
		
	}
  
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		arr = br.readLine();
		map = new Character[n][n];
		
        // map 2차원 배열에 기호를 넣는다
		int idx = 0;
		for(int i = 0; i < n; i++) {
			for(int j = i; j < n; j++) {
				map[i][j] = arr.charAt(idx++);	
			}	
		}
		
        // result : 조건에 만족하여 임의의 숫자를 셋팅한 배열
		result = new int[n];
		dfs(0);
		
	}

}

이 문제의 핵심은 map의 2차원 배열을 만들어서 기호를 넣는 것 이다.
생각을 하지 못했다면.. 풀기가 어려웠을 것 같다.