[백준][1248번] 맞춰봐

문제 URL

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

go 함수

sign[idx][idx]는 idx번째 수의 부호가 들어있다. 이러한 특징을 활용해서

(1) 부호가 0이면 idx자리는 무조건 0이 올 수 밖에없다.

(2) 모든 경우의 수를 계산하면 경우의수가 너무많다. 따라서 단계마다 check 함수를 통해서 가능한 경우만 더 진행하도록 했다.

(3) sign[idx][idx]는 idx번째가 가질수 있는 부호다. 따라서 1~10의 수에 곱해서 계산했다.

public static boolean go(int idx){
    if (idx == size) {
        return true;
    }

//(1)
    if(sign[idx][idx] == '0'){
        ans[idx] = 0;
        return check(idx, 0) && go(idx+1);
    }

//(2)
    for (int k = 1; k <= 10; k++) {
      //(3)
        ans[idx] = k*sign[idx][idx];
        if(check(idx, k*sign[idx][idx]) && go(idx + 1)) {
            return true;
        }
    }
    return false;
}

check 함수

idx번째 자리에 k가 올수있는지 여부 계산하는 함수다.

• sum[i][j] - i부터 j까지의 합이다. 이 변수를 활용해서 idx자리에 k가 올수있는지 검사한다. sum[i][j-1]에 k를 더해서 부호를 검사해주면된다.

public static boolean check(int idx, int k){
    for (int i = idx; i >= 0; i--) {
        if(idx == 0)
            sum[i][idx] = k;
        else
            sum[i][idx] = sum[i][idx-1] + k;

        if (sign[i][idx] == 1 && sum[i][idx] <= 0) {
               return false;
        } else if (sign[i][idx] == -1 && sum[i][idx] >= 0) {
            return false;
        } else if (sign[i][idx] == 0 && sum[i][idx] != 0) {
            return false;
        }
    }

    return true;
}

전체 풀이

package backjoon;

import java.io.*;
import java.util.Arrays;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int size;
    //부호 input 배열
    static int[][] sign;
    // 조건을 만족하는 정답
    static int[] ans;
    //sum[i][j] - i부터 j까지의 합
    static int[][] sum;

    public static void main(String args[]) throws IOException {
        size = Integer.parseInt(br.readLine());
        sign = new int[size][size];
        ans = new int[size];
        sum = new int[size][size];
        String st = br.readLine();

        int cnt = 0;
        for (int i = 0; i < size; i++) {
            for (int j = i; j < size; j++) {
                char x = st.charAt(cnt);
                if (x == '0') {
                    sign[i][j] = 0;
                } else if (x == '+') {
                    sign[i][j] = 1;
                } else {
                    sign[i][j] = -1;
                }
                cnt++;
            }
        }
        go(0);
        for (int i=0; i<size; i++) {
            System.out.print(ans[i] + " ");
        }
    }

    public static boolean go(int idx){
        if (idx == size) {
            return true;
        }

        if(sign[idx][idx] == '0'){
            ans[idx] = 0;
            return check(idx, 0) && go(idx+1);
        }

        for (int k = 1; k <= 10; k++) {
            ans[idx] = k*sign[idx][idx];
            if(check(idx, k*sign[idx][idx]) && go(idx + 1)) {
                return true;
            }
        }
        return false;
    }

    // idx번째 자리에 k가 올수있는지 여부 계산
    public static boolean check(int idx, int k){
        for (int i = idx; i >= 0; i--) {
            if(idx == 0)
                sum[i][idx] = k;
            else
                sum[i][idx] = sum[i][idx-1] + k;

            if (sign[i][idx] == 1 && sum[i][idx] <= 0) {
                   return false;
            } else if (sign[i][idx] == -1 && sum[i][idx] >= 0) {
                return false;
            } else if (sign[i][idx] == 0 && sum[i][idx] != 0) {
                return false;
            }
        }

        return true;
    }
}

느낀점

backtracking을 이용하여 효율을 좀 더 높였다. 단계마다 가능한 자리인지 계산하였다. 가능하지 않다면 더이상 탐색이 의미없으므로 탐색을 중지하도록 했다.

backtracking을 하지않는다면 21개의 수를 10개의 자리에 넣어야하므로 경우의수가 너무 많다.

---

답이 여러가지 나올 수 있는데 한가지만 구하는 문제다. 따라서 한가지 답을 구하면 탐색을 중단해도된다. 이것은 반환타입을 boolean타입을 이용해서 구현할 수 있었다.