공부 176일차: 백준 1248번 Guess 자바 java (문제 해설)

1248 Guess

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

1248번: Guess

 

 

 

---

백준 1248번 문제 Guess

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	8444	3124	1985	35.650%

문제

Given a sequence of integers, a₁, a₂, …, a_n, we define its sign matrix S such that, for 1 ≤ i ≤ j ≤ n, S_ij="+" if a_i + … + a_j > 0; S_ij="−" if a_i + … + a_j < 0; and S_ij="0" otherwise. 

For example, if (a₁, a₂, a₃, a₄)=( −1, 5, −4, 2), then its sign matrix S is a 4×4 matrix: 

	1	2	3	4
1	-	+	0	+
2		+	+	+
3			-	-
4				+

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.

제한

 

예제 입력 1

4
-+0++++--+

예제 출력 1

-2 5 -3 1

예제 입력 2

2
+++

예제 출력 2

3 4

예제 입력 3

5
++0+-+-+--+-+--

예제 출력 3

1 2 -3 4 -5

힌트

 

 

문제를 해석해보면

 

정수배열 a₁, a₂, …, a_n이 주어진다.

1 <= i <= j n일 때, 이것의 부호 행렬 S를 다음과 같이 정의한다
배열의 모든 값을 더했을 때 
양수면 Sij = "+"
음수면 Sij = "-"
0이면 Sij = "0"

예를 들어 배열이 [-1, 5, 4, 2]면 4x4 부호 행렬은 다음과 같이 만들어진다

	1	2	3	4
1	-	+	0	+
2		+	+	+
3			-	-
4				+

배열 [-1, 5, 4, 2]가 그 부호행렬을 만든다.
한 부호 행렬은 정수의 행렬에 의해서 생성될 때에 유효하다.
정수 배얄이 주어질 때, 그것의 부호 행렬을 산출하는 것은 쉽다.
이 문제는 반대 방향에 대한 것이다: 유효한 부호 행렬이 주어질 때, 그 부호 행렬을 만든 정수 배열을 찾아라.
두 개 이상의 서로 다른 정수 배열은 동일한 부호 행렬을 만들 수 있다.
예를 들어, 배열 [-2, 5, -3, 1]은 배열 [-1, 5, -4, 2]와 같은 부호 행렬을 만든다.

주어지는 부호 행렬을 만들어내는 정수 배열을 찾아라.
배열의 모든 정수는 -10 ~ 10 사이이다. (-10, 10 포함)


입력)
첫 번째 줄은 정수 배열의 길이인 n이 주어진다 (1 <= n <= 10)
두 번째 줄은 n(n+1)/2개의 문자열이 주어진다. 처음 n개의 문자는 부호 행렬에 첫 번째 행에 해당하며, 다음 n-1개의 문자는 두 번째 줄, ... 마지막 문자는 n번째 줄에 들어간다.

출력)
해당 부호 행렬을 만드는 n개의 정수 배열을 포함하는 한 줄을 출력한다. 
해당 부호 행렬을 만드는 배열이 한 개 이상이라면, 그 중 아무 것이나 출력하면 된다. 배열의 모든 정수는 무조건 -10과 10 사이의 정수여야 한다.

---

과정 생각해보기

---

 

복잡해 보이지만, 보기 쉽게 정리해보면 다음과 같다

이러한 원리로 위의 부호 행렬 표가 탄생하는 것이다

 

따라서 DFS를 이용하여 위의 조건과 맞을 때마다 배열에 넣어준다

 

 

---

정답 인정 코드

---

 

이 블로그 참고

import java.io.*;
 
public class Main {
 
    static int n;
    static int[] arr;
    static char[][] matrix;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        matrix = new char[n][n];
        String str = br.readLine();
        
        int idx = 0;
        for(int i = 0; i < n; i++) {
            for(int j = i; j < n; j++) {
                matrix[i][j] = str.charAt(idx);    // idx 자리에 idx++ 넣어도 가능
                idx++;
            }
        }
        
//        System.out.println(Arrays.deepToString(matrix));
        DFS(0);
    }
    
    static void DFS(int depth) throws IOException {
        if(depth == n) {
            for(int val : arr) {
                bw.write(val+" ");
            }
            bw.flush();
            bw.close();
            System.exit(0);    // 프로그램 종료
        }
        
        for(int i = -10; i < 11; i++) {
            arr[depth] = i;
            if(check(depth+1)) {    // 그 다음 수가 조건에 맞으면
                DFS(depth+1);    // 재귀 호출(arr의 다음 인덱스 자리에 조건 맞는 숫자 넣기)
            }
        }
    }
    
    static boolean check(int idx) {
        for(int i = 0; i < idx; i++) {
            int sum = 0;
            for(int j = i; j < idx; j++) {
                sum += arr[j];
                if(sum > 0 && matrix[i][j] != '+') {    // 양수인데 해당 자리 기호가 +가 아니라면
                    return false;
                }else if(sum < 0 && matrix[i][j] != '-') {    // 음수인데 해당 자리 기호가 -가 아니라면
                    return false;
                }else if(sum == 0 && matrix[i][j] != '0'){    // 0인데 해당 자리 기호가 0이 아니라면
                    return false;
                }
            }
        }
        return true;
    }
 
}
 

 

 

 

---

DFS는 중요한 개념이지만 다루기 쉽진 않은 것 같다22