[BaekJoon] 1248 Guess (Java)

1.  문제 링크

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

2.  문제

요약

• 정수 수열 $a_1, a_2, ..., a_n$에서 sign matrix S는 다음과 같이 정의됩니다.
  • $a_i + a_{i + 1} + ... + a_j$ > 0이라면 $S_{ij}$는 "+"입니다.
  • $a_i + a_{i + 1} + ... + a_j$ < 0이라면 $S_{ij}$는 "-"입니다.
  • $a_i + a_{i + 1} + ... + a_j$ = 0이라면 $S_{ij}$는 "0"입니다.
• sign matrix가 주어졌을 때, 그러한 sign matrix를 만드는 정수 수열을 구하려고 합니다.
• 같은 sign matrix를 만들 수 있는 두 개 이상의 정수 수열이 존재할 수 있습니다.
• sign matrix가 주어졌을 때, 그러한 sign matrix를 만드는 정수 수열을 찾는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 10보다 작거나 같은 정수 수열의 길이 n이 주어지고 두 번째 줄에 n * (n + 1) / 2개의 문자들이 주어집니. 첫 n개의 문자는 sign matrix의 첫 번째 행을 의미하고, 다음 n - 1개의 문자는 sign matrix의 두 번째 행을 의미하며, ..., 마지막 문자는 n번째 행을 의미합니다.
• 출력: 첫 번째 줄에 정수 수열을 출력합니다. 주어진 sign matrix를 만들 수 있는 수열이 2개 이상이라면, 그들 중 아무거나 하나를 출력합니다. 수열에 있는 모든 정수는 -10 이상 10 이하의 정수입니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int n;
    static char[][] signMatrix;
    static int[] sequence;

    static void input() {
        Reader scanner = new Reader();

        n = scanner.nextInt();
        signMatrix = new char[n + 1][n + 1];
        sequence = new int[n + 1];

        String info = scanner.nextLine();
        int index = 0;
        for(int row = 1; row <= n; row++) {
            for(int col = row; col <= n; col++) {
                signMatrix[row][col] = info.charAt(index);
                index++;
            }
        }
    }

    static void solution() {
        recFunc(1);
    }

    static void recFunc(int index) {
        if(index > n) {
            for(int idx = 1; idx <= n; idx++) System.out.print(sequence[idx] + " ");
            System.exit(0);
        }

        for(int num = -10; num <= 10; num++) {
            sequence[index] = num;
            if(isPossible(index)) recFunc(index + 1);
        }
    }

    static boolean isPossible(int index) {
        for(int start = 1; start <= index; start++) {
            int sum = 0;
            for(int idx = start; idx <= index; idx++) {
                sum += sequence[idx];
                if(signMatrix[start][idx] != (sum > 0 ? '+' : (sum == 0 ? '0' : '-')))
                    return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }

            return str;
        }
    }
}