21.05.30 - [BOJ] 1248. 맞춰봐

[suhyunsim]

문제

• 1248

핵심 아이디어

• -10부터 10까지 N개의 정수로 이루어진 수열 A가 있다.(N≤10)
• S[i][j]=A[i]+A[i+1]+...+A[j]가 0보다 크면 +, 작으면 -, 같으면 0
• S가 주어졌을 때, 가능한 A를 아무거나 찾는 문제
• 위치 N개, 각각의 위치에 넣을 수 있는 수: 21개(-10 ~ 10) -> 21개의 수를 10개의 자리에 넣어야 함 -> 브루트포스 X
• S[i][i]의 부호는 A[i]의 부호와 같음 -> 경우의 수가 줄어듬
  • -10 ~ +10까지 순회 X -> 양수일 때는 1 ~ 10, 음수일 때는 -10 ~ -1, 0인 경우 0을 넣는 방식으로 개선할 수 있음
    
• index번째 수를 결정하면, 0 ~ index번째 수는 변하지 않는다.
  => 모든 sign[k][index] (0 <= k < index)를 go(index)에서 검사할 수 있다.
• check(index): index번째의 수 결정
• S[i][index]: index번째까지의 합을 모두 구해서 index번째와 같은지 확인

어려운 점, 실수

• 시간초과 해결하는 방법을 이해하지 못함(단순히 브루트포스로만 풀 생각밖에 없었음)

풀이

package main.java.com.poogle.BOJ.Q1248;

import java.util.Scanner;

public class Main {
    static int n;
    static int[] answer;
    static int[][] sign;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        answer = 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 if (x == '-') {
                    sign[i][j] = -1;
                }
                cnt += 1;
            }
        }
        go(0);
        for (int i = 0; i < n; i++) {
            System.out.println(answer[i] + " ");
        }
        System.out.println();
    }

    private static boolean go(int index) {
        if (index == n) {
            return true;
        }
        if (sign[index][index] == 0) {
            answer[index] = 0;
            return check(index) && go(index + 1);
        }
        //index번째 수를 i라고 결정했다고 가정, 검사하기 -1 ~ -10도 가능
        for (int i = 1; i <= 10; i++) {
            answer[index] = sign[index][index] * i;
            if (check(index) && go(index + 1)) return true;
        }
        return false;
    }

    private static boolean check(int index) {
        int sum = 0;
        for (int i = index; i >= 0; i--) {
            sum += answer[i];
            if (sign[i][index] == 0) {
                if (sum != 0) return false;
            } else if (sign[i][index] < 0) {
                if (sum >= 0) return false;
            } else if (sign[i][index] > 0) {
                if (sum <= 0) return false;
            }
        }
        return true;
    }
}