1248번: 맞춰봐
규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느 날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 수도
www.acmicpc.net
#include <iostream>
#include <string>
using namespace std;
int n;
int sign[10][10];
int ans[10];
bool ok() {
for (int i=0; i<n; i++) {
int sum = 0;
for (int j=i; j<n; j++) {
sum += ans[j];
if (sign[i][j] == 0) {
if (sum != 0) return false;
} else if (sign[i][j] > 0) {
if (sum <= 0) return false;
} else if (sign[i][j] < 0) {
if (sum >= 0) return false;
}
}
}
return true;
}
bool go(int index) {
if (index == n) {
return ok();
}
for (int i=-10; i<=10; i++) {
ans[index] = i;
if (go(index+1)) return true;
}
return false;
}
int main() {
cin >> n;
string s;
cin >> s;
int cnt = 0;
for (int i=0; i<n; i++) {
for (int j=i; j<n; j++) {
if (s[cnt] == '0') {
sign[i][j] = 0;
} else if (s[cnt] == '+') {
sign[i][j] = 1;
} else {
sign[i][j] = -1;
}
cnt += 1;
}
}
go(0);
for (int i=0; i<n; i++) {
cout << ans[i] << ' ';
}
cout << '\n';
return 0;
}
#include <iostream>
#include <string>
using namespace std;
int n;
int sign[10][10];
int ans[10];
bool ok() {
for (int i=0; i<n; i++) {
int sum = 0;
for (int j=i; j<n; j++) {
sum += ans[j];
if (sign[i][j] == 0) {
if (sum != 0) return false;
} else if (sign[i][j] > 0) {
if (sum <= 0) return false;
} else if (sign[i][j] < 0) {
if (sum >= 0) return false;
}
}
}
return true;
}
bool go(int index) {
if (index == n) {
return ok();
}
if (sign[index][index] == 0) {
ans[index] = 0;
return go(index+1);
}
for (int i=1; i<=10; i++) {
ans[index] = sign[index][index]*i;
if (go(index+1)) return true;
}
return false;
}
int main() {
cin >> n;
string s;
cin >> s;
int cnt = 0;
for (int i=0; i<n; i++) {
for (int j=i; j<n; j++) {
if (s[cnt] == '0') {
sign[i][j] = 0;
} else if (s[cnt] == '+') {
sign[i][j] = 1;
} else {
sign[i][j] = -1;
}
cnt += 1;
}
}
go(0);
for (int i=0; i<n; i++) {
cout << ans[i] << ' ';
}
cout << '\n';
return 0;
}
#include <iostream>
#include <string>
using namespace std;
int n;
int sign[10][10];
int ans[10];
bool check(int index) {
int sum = 0;
for (int i=index; i>=0; i--) {
sum += ans[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;
}
bool go(int index) {
if (index == n) {
return true;
}
if (sign[index][index] == 0) {
ans[index] = 0;
return check(index) && go(index+1);
}
for (int i=1; i<=10; i++) {
ans[index] = sign[index][index]*i;
if (check(index) && go(index+1)) return true;
}
return false;
}
int main() {
cin >> n;
string s;
cin >> s;
int cnt = 0;
for (int i=0; i<n; i++) {
for (int j=i; j<n; j++) {
if (s[cnt] == '0') {
sign[i][j] = 0;
} else if (s[cnt] == '+') {
sign[i][j] = 1;
} else {
sign[i][j] = -1;
}
cnt += 1;
}
}
go(0);
for (int i=0; i<n; i++) {
cout << ans[i] << ' ';
}
cout << '\n';
return 0;
}'Problem set' 카테고리의 다른 글
| [백준] 1182 부분수열의 합 (0) | 2021.02.20 |
|---|---|
| [백준] 11723 집합 (0) | 2021.02.20 |
| [백준] 2529 부등호 (0) | 2021.02.20 |
| [백준] 15661 링크와 스타트 (0) | 2021.02.20 |
| [백준] 14889 스타트와 링크 (0) | 2021.02.20 |