PS 시나브로

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

문제 요약 : 수를 조합하여 주어진 부호에 맞는 숫자 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_1248.java

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

public class Main {
	
	static int[][] op;
	static int[] arr;
	static int n;
	static boolean chk;
    static StringBuilder sb = new StringBuilder();
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int i,j,k;
		n = Integer.parseInt(br.readLine());
		op = new int[n][n];
		arr = new int[n+1];
		String str = br.readLine();
		k = 0;
		for(i=0;i<n;i++) {
			for(j=i;j<n;j++) {
				if(str.charAt(k)=='-') {
					op[i][j] = -1;
				}else if(str.charAt(k)=='0') {
					op[i][j] = 0;
				}else {
					op[i][j] = 1;
				}
				k++;
			}
		}
		chk = false;
		btr(0);
		System.out.println(sb);
	}
	
	static void btr(int k) {
		if(chk) return;
		if(k==n) {
			for(int i=1;i<=n;i++) sb.append((arr[i]-arr[i-1])+" ");
			chk = true;
			return;
		}
		int mx = 10;
		int mi = -10;
		for(int i=0;i<=k;i++) {
			if(op[i][k]==-1) {
				mx = Math.min(mx, arr[i]-arr[k]-1);
			}else if(op[i][k]==0) {
				mx = Math.min(mx, arr[i]-arr[k]);
				mi = Math.max(mi, arr[i]-arr[k]);
			}else {
				mi = Math.max(mi, arr[i]-arr[k]+1);
			}
		}
		for(int i=mi;i<=mx;i++) {
			arr[k+1] = arr[k] + i;
			btr(k+1);
		}
	}
}

숫자를 앞에서 부터 가능한 숫자를 구하여 가능한 모든 경우를 확인한다.

숫자의 범위가 -10 부터 10이므로 초기값을 최소 -10, 최대 10으로 설정 한 후

해당 순번의 부분합 부호를 확인하며 들어갈 수 있는 최소 또는 최대 값을 수정하며 탐색한다.

예제 )

4
-+0++++--+