맞춰봐

📍 문제 설명

 

💡 접근

1.주어진 문자열을 S[i][j]의 위치에 맞게 넣는다.

2.규현이가 아는 숫자 -10 ~ 10을 탐색한다.

3.현재 인덱스에 사용할 숫자를 기록한다.

4.현재까지의 인덱스까지의 합이 S[i][j]의 값과 맞는지 비교한다.

5.여기까지 통과하면 다음 인덱스 숫자를 구해본다.

6.N개의 숫자를 구했으면 답을 하나만 출력하기 위해 바로 종료시킨다.

 

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, sum, answer;
    static char[][] board,clone;
    static char[] c;
    static int[] arr;
    static boolean[] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        Main T = new Main();
        n = kb.nextInt();
        kb.nextLine();
        c = kb.nextLine().toCharArray();
        int idx = 0;
        board = new char[n][n];

        //문자열로 주어진 S[i][j]를 기록
        for(int i = 0; i < n; i++) {
            for(int j = i; j < n; j++) {
                board[i][j] = c[idx++];
            }
        }
        //수열의 원소 담을 배열
        arr = new int[n];
        T.solution(0);
    }

    private void solution(int L) {
        //올바른 숫자 4개 뽑음
        if(L == n) {
            for(int x : arr) System.out.print(x + " ");
            System.out.println();
        }
        else {
            //규현이가 아는 모든 숫자에 대해서 탐색
            for(int i = -10; i <= 10; i++) {
                //현재 인덱스의 숫자를 기록
                arr[L] = i;
                //기록한 인덱스까지 올바른 부호를 가지고 있는지 확인
                if(check(L)) solution(L+1);
            }
        }
    }

    private boolean check(int L) {
        for(int i = 0; i <= L; i++) {
            int sum = 0;
            for(int j = i; j <= L; j++) {
                sum += arr[j];
                //board에 담겨있는 부호와 다르면 false
                if(board[i][j] != (sum == 0 ? '0' : (sum > 0 ? '+' : '-'))) {
                    return false;
                }
            }
        }
        return true;
    }
}