본문 바로가기

BOJ

백준 1248 / 맞춰봐




문제 설명에 온갖 말장난을 쳐놔서 이해하는데 오랜 시간이 걸렸다.


요약하자면, -10~10, 총 21개의 수로 입력받은 결과를 만족하는 n개의 수를 찾는 문제.



중복이 가능하기 떄문에 총 21^n개의 경우의수가 발생한다. (n=10일 경우 시간초과가 무조건 발생한다)


그렇기에 몇몇 체크를 추가하여 걸리는 시간을 줄여야 한다.


여기서 관찰력과 아이디어가 필요한데,


입력받은 부호(-,0,+)중 S[i][i]는 i의 부호를 말하고 있다는 점이다.



그러나 이 점을 활용하여 코드를 구성해도 시간초과가 걸린다.



여기서 또 하나 체크를 추가해주어야한다.


정답 배열 ans에 담긴 숫자가 n이 될때마다 체크를 하지말고,


숫자가 담길떄 마다 체크를 실행하는 것이다.



이런 자잘한 아이디어를 생각해내기 힘들기 떄문에 굉장히 어려운 문제이다.



코드


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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<stdio.h>
#include<vector>
#include<queue>
#include<iostream>
 
using namespace std;
 
 
int buho[10][10];
 
vector<int>ans;
 
int n;
 
bool check(int index) {
    int sum = 0;
    for (int i = index; i >= 0; i--) {
        sum += ans[i];
        if (buho[i][index] == 0) {
            if (sum != 0)return false;
        }
        if (buho[i][index] < 0) {
            if (sum >= 0)return false;
        }
        if (buho[i][index] > 0) {
            if (sum <= 0)return false;
        }
 
    }
    return true;
}
 
bool go(int index) {
    if (index == n) {
        return true;
    }
    if (buho[index][index] == 0) {
        ans[index] = 0;
        return check(index) && go(index + 1);
    }
 
    for (int i = 1; i <= 10; i++) {
        ans[index] = buho[index][index] * i;
        if (check(index) && go(index + 1))
            return true;
 
    }
 
    return false;
}
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
 
    cin >> n;
    ans.resize(n);
 
 
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            char c;
            cin >> c;
            if (c == '0') {
                buho[i][j] = 0;
            }
            if (c == '+') {
                buho[i][j] = 1;
            }
            if (c == '-') {
                buho[i][j]=-1;
            }
 
        }
    }
 
    go(0);
    
    for (int i = 0; i < n; i++) {
        cout << ans[i] << " ";
    }
    
}
cs


'BOJ' 카테고리의 다른 글

백준 2580 / 스도쿠  (0) 2019.01.22
백준 9663 / N-Queen  (0) 2019.01.21
백준 14889 / 스타트와 링크  (0) 2019.01.19
백준 1339 / 단어 수학  (0) 2019.01.19
백준 2529 / 부등호  (0) 2019.01.18