문제 설명에 온갖 말장난을 쳐놔서 이해하는데 오랜 시간이 걸렸다.
요약하자면, -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 |