백준 1248 Guess (Java)

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

1. 문제

Given a sequence of integers, a1, a2, …, an, we define its sign matrix S such that, for 1 ≤ i ≤ j ≤ n, Sij="+" if ai + … + aj > 0; Sij="−" if ai + … + aj < 0; and Sij="0" otherwise. 

For example, if (a1, a2, a3, a4)=( −1, 5, −4, 2), then its sign matrix S is a 4×4 matrix: 

-	+	0	+
	+	+	+
		-	-
			+

We say that the sequence (−1, 5, −4, 2) generates the sign matrix. A sign matrix is valid if it can be generated by a sequence of integers. 

Given a sequence of integers, it is easy to compute its sign matrix. This problem is about the opposite direction: Given a valid sign matrix, find a sequence of integers that generates the sign matrix. Note that two or more different sequences of integers can generate the same sign matrix. For example, the sequence (−2, 5, −3, 1) generates the same sign matrix as the sequence (−1,5, −4,2). 

Write a program that, given a valid sign matrix, can find a sequence of integers that generates the sign matrix. You may assume that every integer in a sequence is between −10 and 10, both inclusive. 

입력

The first line contains an integer n(1 ≤ n ≤ 10), where n is the length of a sequence of integers. The second line contains a string of n(n+1)/2 characters such that the first n characters correspond to the first row of the sign matrix, the next n−1 characters  to the second row, ..., and the last character to the n-th row. 

출력

Output exactly one line containing a sequence of n integers which generates the sign matrix. If more than one sequence generates the sign matrix, you may output any one of them. Every integer in the sequence must be between −10 and 10, both inclusive.

 

2. 풀이

위의 표 S에서 i열 j행의 기호는 n개의 숫자가 있을 때 i번째 수부터 j번째 수까지 더한 결과를 나타낸다. 만약 1행 2열이면 +이고, {-1, 5, -4. 2}가 주어졌을 때 1번째 수와 2번째 수를 더하면 4, +가 된다. 이런 식으로 기호가 주어졌을 때 이를 만족하는 숫자 배열을 아무거나 하나 출력하는 문제이다. 각 숫자는 -10부터 10까지 허용된다.

 

        input = reader.readLine();
        map = new char[n][n];

        int idx = 0;
        for(int i = 0; i < n; i++) {
            for(int j = i; j < n; j++) {
                map[i][j] = input.charAt(idx++);
            }
        }

 기호를 입력받고, 2차원 문자 배열에 순서대로 넣어준다.

 

    private static void dfs(int cnt) {

        if (cnt == n) {
            for (Integer i : hist) {
                System.out.print(i + " ");
            }
            exit(0);
        }

        for (int i = -10; i <= 10; i++) {
            hist[cnt] = i;
            if (check(cnt + 1)) {
                dfs(cnt + 1);
            }
        }
    }

이제 숫자를 만들어나간다. 모든 경우를 탐색하면 메모리 초과가 나므로 -10부터 10까지 숫자를 하나씩 넣어 표의 조건을 만족하면 다음 숫자를 집어넣는 느낌의 dfs를 구현했다.

 

    //생성한 숫자로 알맞은 기호를 만들 수 있는 지 확인
    private static boolean check(int cnt) {


        for (int i = 0; i < cnt; i++) {
            int sum = 0;
            for (int j = i; j < cnt; j++) {
                sum += hist[j];
                if (map[i][j] == '+' && sum <= 0) {
                    return false;
                }
                if (map[i][j] == '0' && sum != 0) {
                    return false;
                }
                if (map[i][j] == '-' && sum >= 0) {
                    return false;
                }

            }
        }

        return true;
    }

 cnt개의 숫자를 만들었을 때 조건을 확인하는 메서드이다. 1번째 수부터 cnt번째 수까지의 모든 부분합을 찾아가면서 표의 부호와 비교한 후 하나라도 맞지 않다면 false, 모두 넘어갔다면 true를 리턴한다.

 

 모든 경우를 뚫고 숫자를 만들었다면 이를 출력하고 프로그램을 종료한다.

 

3. 코드 전문

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

import static java.lang.System.exit;

public class Main {

    static int n;

    static String input;

    static char[][] map;

    static int[] hist;

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

        n = Integer.parseInt(reader.readLine());
        input = reader.readLine();
        map = new char[n][n];

        int idx = 0;
        for(int i = 0; i < n; i++) {
            for(int j = i; j < n; j++) {
                map[i][j] = input.charAt(idx++);
            }
        }


        hist = new int[n];

        dfs(0);


    }

    //힌트를 기반으로 숫자들을 만들어 나감
    private static void dfs(int cnt) {

        if (cnt == n) {
            for (Integer i : hist) {
                System.out.print(i + " ");
            }
            exit(0);
        }

        for (int i = -10; i <= 10; i++) {
            hist[cnt] = i;
            if (check(cnt + 1)) {
                dfs(cnt + 1);
            }
        }
    }

    //생성한 숫자로 알맞은 기호를 만들 수 있는 지 확인
    private static boolean check(int cnt) {


        for (int i = 0; i < cnt; i++) {
            int sum = 0;
            for (int j = i; j < cnt; j++) {
                sum += hist[j];
                if (map[i][j] == '+' && sum <= 0) {
                    return false;
                }
                if (map[i][j] == '0' && sum != 0) {
                    return false;
                }
                if (map[i][j] == '-' && sum >= 0) {
                    return false;
                }

            }
        }

        return true;
    }
}