https://www.acmicpc.net/problem/1248
1248번: 맞춰봐
규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느 날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 수도
www.acmicpc.net
🔔 문제 :
문제가 길어 이해하기 난해했던 문제였습니다.
정리를 해보면
N <= 10 조건의 자연수 N이 주어지고
N(N+1)/2 길이의 (+, -, 0 중 하나인) 문자열이 주어집니다.
또한 숫자의 범위는 -10 <= x <= 10 입니다
이 문자열의 정체는 N에 적혀있는 숫자의 순서에 따라서 합한 값의 부호입니다.
예를 들어 개수가 N = 4인 숫자 -2 5 -3 1 가 있습니다.
그리고 부호는 -+0++++--+ 입니다.
부호 10개중의 순서대로
첫번째 - : (-2) < 0
두번째 + : (-2 + 5) > 0
세번째 0 : (-2 + 5 -3) = 0
네번째 + : (-2 + 5 -3 + 1) > 0
다섯번째 + : (5) > 0
여섯번째 + : (5 - 3) > 0
일곱번째 + : (5 -3 + 1) > 0
여덟번째 - : (-3) < 0
아홉번째 - : (-3 +1 ) < 07
열번째 + : (1) > 0
이런 조건으로 흘러가는 숫자 (-2 5 -3 1) 처럼 주어진 부호의 조건에 맞는 숫자를 구하면 되는 문제입니다.
🔔 Kick Point :
숫자의 크기가 -10 <= N <= 10 이기에 재귀적 함수를 사용하여 자리 수마다 차례차례 넣어보면 되는 문제입니다.
저는 -10 부터 시작하여 10까지 진행하였습니다.
그리고 조건을 확인해보아 맞으면 진행 할 수 있도록 합니다.
🔔 Code :
G_n : 숫자 크기
G_select[MAX] : 자리수마다 들어간 숫자배열
G_operators[MAX][MAX] : 주어진 문자배열
#include <iostream>
using namespace std;
#define MAX 10
#define endl '\n'
int G_n;
int G_select[MAX];
char G_operators[MAX][MAX];
void Input(int n) {
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
cin >> G_operators[i][j];
}
}
}
bool Check(int idx) {
int Sum = 0;
for (int i = idx; i >= 0; i--) {
Sum += G_select[i];
if (G_operators[i][idx] == '+' && Sum <= 0) return false;
if (G_operators[i][idx] == '-' && Sum >= 0) return false;
if (G_operators[i][idx] == '0' && Sum != 0) return false;
}
return true;
}
void DFS(int cnt = 0 ) {
if (cnt == G_n) {
for (int i = 0; i < G_n; i++) {
cout << G_select[i] << " ";
}
cout << endl;
exit(0);
}
for (int i = -10; i <= 10; i++) {
G_select[cnt] = i;
if (Check(cnt) == true) DFS(cnt + 1);
}
}
int main() {
cin >> G_n;
Input(G_n);
DFS();
}