백준 1248 / 맞춰봐

문제

풀이

설명

-10 부터 10까지 N개의 정수(중복없음)로 이루어진 수열 A가 있다.(N<=10)
S[i][j] = A[i]+A[i+1]+...+A[j]가 0보다 크면 +, 작으면-, 같으면 0
S가 주어졌을 때, 가능한 A를 아무거나 찾는 문제

21개의 수를 10개의 자리(A[i])에 넣어야 한다.
총 경우의 수 : 21^10 = 16,679,880,978,201
경우의 수가 너무 많다.
그래도 일단 함수를 작성해보자.

bool go(int index) {
	if(index == n) {
    	return ok();
    }
    for (int i = -10; i<=10; i++) {
    	ans[index] = i;
        if (go(index+1)) {
        	return true;
        }
    return false;
}

이렇게도 풀 수 있고

두번째 방법은

위 그림의 [0][0],[1][1],[2][2],[3][3] 부분을 보면 결과가 +이면 양수 -이면 음수임을 알 수 있고 이것을 이용해 푸는 방법을 알아보자

sign[i][i]에는 i번째 수의 부호가 들어있다.
-10에서 10까지 순회하지 않고 양수인 경우 1~10까지, 음수인 경우 -10 ~ -1까지, 0인 경우 0 까지 넣는 방식으로 개선해 볼 수 있다.

이렇게 계산하면 10^10 크기의 경우의 수가 생긴다.
코드로 표현하면

bool go(int index) {
	if(index == n) {
    	return ok();
    }
    if(sign[index][index] == 0) {
    	ans[index] = 0;
        return go(index+1);
    }
    for (int i = -10; i<=10; i++) {
    	ans[index] = i;
        if (go(index+1)) {
        	return true;
        }
    return false;
}

하지만 두번째 방법도 10^10으로 그리 적은 탐색 수라고 보기 어렵다
따라서 더 나은 방법을 통해 문제를 풀어야 한다.

세번째 방법은 위 그림을 봤을 때 0~3, 1~3, 2~3, 3~3 을 탐색한다면
index번째의 수를 결정하면 (0~ (index))수가 결정되었다는 것이므로
모든 sign[k][index] (0 <= k < index)를 go(index)에서 검사할 수 있다.

bool go(int index) {
	if(index == n) {
    	return true;
    }
    if(sign[index][index] == 0) {
    	ans[index] = 0;
        return check(index) && go(index+1);
    }
    for (int i = -10; i<=10; i++) {
    	ans[index] = sign[index][index]*i;
        if (check(index) && go(index+1)) {
        	return true;
        }
    return false;
}

코드

import java.util.*;

public class num1248 {
    static int n;
    static int[][] sign;
    static int[] ans;
    static boolean ok() {
        for (int i=0; i<n; i++) {
            int sum = 0;
            for (int j=i; j<n; j++) {
                sum += ans[j];
                if (sign[i][j] == 0) {
                    if (sum != 0) return false;
                } else if (sign[i][j] > 0) {
                    if (sum <= 0) return false;
                } else if (sign[i][j] < 0) {
                    if (sum >= 0) return false;
                }
            }
        }
        return true;
    }
    static boolean go(int index) {
        if (index == n) {
            return ok();
        }
        for (int i=-10; i<=10; i++) {
            ans[index] = i;
            if (go(index+1)) return true;
        }
        return false;
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        ans = new int[n];
        sign = new int[n][n];
        String s = sc.next();
        int cnt = 0;
        for (int i=0; i<n; i++) {
            for (int j=i; j<n; j++) {
                char x = s.charAt(cnt);
                if (x == '0') {
                    sign[i][j] = 0;
                } else if (x == '+') {
                    sign[i][j] = 1;
                } else {
                    sign[i][j] = -1;
                }
                cnt += 1;
            }
        }
        go(0);
        for (int i=0; i<n; i++) {
            System.out.print(ans[i] + " ");
        }
        System.out.println();
    }
}

코드설명

출처

문제

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

참고