백준/1248 맞춰봐

작성일 | In

< 문제 분석 및 풀이 방법 >

Backjoon :: 맞춰봐 문제는 브루드 포스 방식을 활용했다.

  • 길이 n의 배열을 만들 때 모든 경우의 수를 실행해본다.
  • 처음 입력받은 문자를 잘 보면 checkMark[1][1] 은 첫 번째 숫자의 부호를 나타낸다.
  1. 첫 번째 스위치를 누르고 시작하는 경우 / 누르지 않고 시작하는 경우 로 나눠 시작한다.
  2. 두 번째 스위치부터 n-1 번째 스위치 값과 비교한다.
    1. input[n-1] == target[n-1] 이라면 스위치를 누르지 않는다.
    2. input[n-1] != target[n-1] 이라면 스위치를 누른다.
    3. (총 길이 - 1) 번째 까지 반복한다.
  3. (총 길이 - 1) 에 접근 시 스위치를 누를 때 / 누르지 않을 때를 비교한다.

< 소스 코드 >

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.io.*;
import java.util.*;

public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int n;
    public static int[] num;            //n개의 숫자 만드는 배
    public static String mark;          //입력받은 부호
    public static boolean[] isUsedNumber;     //0~10 숫자 사용 여부
    public static char[][] checkMark;     //Mark 저장하는 배열

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        num = new int[n];
        isUsedNumber = new boolean[11];
        checkMark = new char[n][n];
        mark = br.readLine();
        int idx = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                checkMark[i][j] = mark.charAt(idx++);
            }
//            System.out.println(Arrays.toString(checkMark[i]));
        }

        getPermutation(0);
//        System.out.println(sb);
    }

    public static void getPermutation(int idx) {
        boolean isAnswer = isPossible(idx);     //여태까지 만들어진 순열과 부호와 비교
        if (!isAnswer) return;                  //불가능하다면 가지치기
        if (idx == n) {
            for (int i = 0; i < n; i++) {
                sb.append(num[i] + " ");
            }
            System.out.println(sb);
            System.exit(0);
        }
        //모든 경우의 수를 만들어보자
        for (int i = 0; i <= 10; i++) {
            if (checkMark[idx][idx] == '+') num[idx] = -i + 10;
            if (checkMark[idx][idx] == '0') num[idx] = 0;
            if (checkMark[idx][idx] == '-') num[idx] = i - 10;
            getPermutation(idx + 1);
        }
    }

    public static boolean isPossible(int n) {   //만든 배열로 입력받은 문자를 만들수 있는지 확인
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += num[j];
                if (checkMark[i][j] == '+' && sum <= 0) return false;
                if (checkMark[i][j] == '0' && sum != 0) return false;
                if (checkMark[i][j] == '-' && sum >= 0) return false;
            }
        }
        return true;
    }
}