[백준] 1248번 맞춰봐

1248번 맞춰봐

---

1. 이해하기

• 설명은 길게 되어 있지만 결국은 N개의 숫자를 선택하는 문제이다. 하지만 부호를 잘 맞춰야 하는 문제이다.
• 완전 탐색과 백트랙킹으로 풀 수 있다.

---

2. 구현하기

• solve(index)

  • index를 N까지 진행해보며 N에 도달했다면 true를 반환한다.

  • 0 ~ 20 부터 반복하면서 result배열에 하나씩 넣어본다. 이때 -10을 하고 넣어줘서 -10 ~ 10의 구간을 만들어준다.

  • 이때 가장 중요한 것은 추가를 했을 때, 바로 가능한 경우인지를 비교해줘서 체크를 해야 시간 초과 등의 문제를 피할 수 있다.

    static boolean solve(int index) {
      if(index == N)
          return true;
    
      for(int i = 0; i <= 20; i++) {
          result[index] = i-10;
          if(check(index) && solve(index+1))
              return true;
      }
      return false;
    }

• check(index)

  • 현재까지 정한 수들이 결과가 맞게 나오는 수들인지 체크하는 함수이다.

  • 부호들이 저장되어 있는 buho[][] 배열을 이용하여 i ~ index 까지의 부호가 맞게 설정이 되어 있는지를 비교한다.

    static boolean check(int index) {
      int sum = 0;
      for(int i = index; i >= 0; i--) {
          sum += result[i];
          if(buho[i][index] == 0 && sum != 0)
              return false;
          if(buho[i][index] < 0 && sum >= 0)
              return false;
          if(buho[i][index] > 0 && sum <= 0)
              return false;
      }
      return true;
    }

---

3. 전체코드

import java.util.Scanner;

public class Main {
    static int N;
    static String str;
    static char[] cArr;
    static int[][] buho;
    static int[] result;
    static int[] sum;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        sc.nextLine();
        str = sc.nextLine();
        result = new int[N];
        buho = new int[N][N];
        sum = new int[N+1];
        int strIdx = 0;
        for(int i = 0; i < N; i++) {
            for(int j = i; j < N; j++) {
                if(str.charAt((strIdx)) == '-')
                    buho[i][j] = -1;
                else if(str.charAt(strIdx) == '0')
                    buho[i][j] = 0;
                else if(str.charAt(strIdx) == '+')
                    buho[i][j] = 1;
                strIdx++;
            }
        }
        solve(0);
        for(int i = 0; i < N; i++)
            System.out.print(result[i]+" ");
        sc.close();
    }

    static boolean solve(int index) {
        if(index == N)
            return true;

        for(int i = 0; i <= 20; i++) {
            result[index] = i-10;
            if(check(index) && solve(index+1))
                return true;
        }
        return false;
    }

    static boolean check(int index) {
        int sum = 0;
        for(int i = index; i >= 0; i--) {
            sum += result[i];
            if(buho[i][index] == 0 && sum != 0)
                return false;
            if(buho[i][index] < 0 && sum >= 0)
                return false;
            if(buho[i][index] > 0 && sum <= 0)
                return false;
        }
        return true;
    }
}