음 문제가 엄청 길다.
필요한 내용이 중간 중간 있을까봐 전부 꼼꼼히 읽었지만 마지막 부분만 읽으면 된다..
규현이는 -10~10까지 알고 있기 때문에 총 21가지 수를 쓸 수 있다(0포함)
만약에 규현이가
A= [-2, 5, -3, 1]이라는 수를 말한다면 이것을 2차원 배열 S에 다음과 같이 표현할 수 있다.
| 0 | 1 | 2 | 3 | |
| 0 | - | + | 0 | + |
| 1 | X | + | + | + |
| 2 | X | X | - | - |
| 3 | X | X | X | + |
S[i][j]는 A[i]부터 A[j]까지의 합이 양수면 +, 음수면 -, 0이면 0을 나타낸다.
여기서 i는 j보다 작거나 같아야 한다.
i가0이고 j가 1이라 해보자 A[0]+A[1]이 되고 이것의 합은 3이기 때문에 S[0][1]에 +가 저장된다.
i가 0이고 j가 2이라면 A[0]+A[1]+A[2]가 되고 이 합은 0이기 때문에 S[0][2]에 0이 저장된다.
S[1][0]의 경우 i(1)가 j(0)보다 크기 때문에 X가 들어간다.
접근
문제에서 A 배열을 주고 S 이차원 배열을 만드는 것이 아니라
S 이차원 배열을 주고 A 배열을 만들어야 한다. 즉 역으로 구해야 한다.
브루트 포스로 풀게 되면 N의 크기 만큼 A 배열에 -10~10까지 21가지 수를 랜덤하게 넣어서 풀어야 하는데
N은 10보다 작거나 같으니 최대 21의 10제곱의 경우의 수가 나온다.
ex. A= [21가지 경우의 수, 21가지 경우의 수 ..... ,21가지 경우의 수]->21^10
S 이차원 배열을 보면 i와 j가 같을때 A[i]의 수가 어떤 범위에 속할지 알 수 있다.
주어진 S가 위와 같다고 했을 때 S[0][0]은 -이므로 A[0]은 0~10까지의 수는 올 수가 없다.
또 S[1][1]은 +이므로 -10~0까지의 수는 올 수가 없다.
이런 식으로 각 A[i]의 범위를 한정지을 수 있다.
하지만 이렇게 각 수의 범위를 한정 지어도 최악의 경우 각 범위는 10일 테니 10의 N제곱 만큼의 경우의 수가 나온다.
N의 최대 값은 10이니 10의 10제곱도 여전히 경우의 수가 크다.
따라서 백 트래킹을 통해 더이상 의미 없는 조건은 실행시키지 않도록 한다.
여기서 의미 없는 조건은 A배열을 만들다 보면 S[i][j]에 해당하지 않는 수가 있는데 이런 경우 A배열에 수를 추가하는 것이 아니라 추가 된 수를 변경해주어야 한다.
ex. A에 -4, 2가 있다고 했을 때 이 수는 S [0][1]의 조건과 맞지 않다.
그래서 다음과 같이 구현해 보았다.
isThisRight에서 현재까지 만들어진 A배열을 통해 S[i][j]에 들어갈 값을 만드는데 이때 실제 S[i][j]값과 일치하는지 확인한다. 일치하지 않는게 있다면 A 배열에 입력된 수가 잘못되었기 때문에 입력된 수를 다시 넣어준다.
하지만 isThisRight함수에서 비교하는 함수의 호출도 빈번하고 시간도 오래 걸려서 시간초과가 뜬다.
#include <iostream>
#include <string>
using namespace std;
char S[10][10];
int N, A[10];
bool isThisRight(int idx){
for(int low=0; low<idx; low++){
int sum=A[low];
char state;
for(int col=low+1; col<idx; col++){
sum+=A[col];
if(sum > 0) state = '+';
else if(sum < 0) state = '-';
else state ='0';
if(state != S[low][col]) return false;
}
}
return true;
}
bool guessMe(int idx){
if(idx == N){
if( !isThisRight(idx) ) return false;
for(int k=0; k<N; k++){
cout << A[k] << ' ';
}
cout << '\n';
return true;
}
char curState = S[idx][idx];
bool flag;
if(curState == '+'){
for(int i=1; i<=10; i++){
A[idx] = i;
flag = guessMe(idx+1);
if(flag) return true;
}
}
else if(curState == '-'){
for(int i=-1; i>=-10; i--){
A[idx] = i;
flag = guessMe(idx+1);
if(flag) return true;
}
}
else {
A[idx] = 0;
flag = guessMe(idx+1);
if(flag) return true;
}
}
int main()
{
int strIdx=0;
string str;
cin >> N >> str;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(i>j){
S[i][j] = 'X';
continue;
}
S[i][j] = str[strIdx++];
}
}
guessMe(0);
return 0;
}
그래서 isThisRight함수를 S 이차원 배열 전부를 검사하는 것이 아니라 필요한 부분만 검사하도록 수정하였다.
#include <iostream>
#include <string>
using namespace std;
char S[10][10];
int N, A[10];
bool isThisRight(int idx){
int sum = 0;
for(int low=idx; low>=0; low--){
sum+=A[low];
char state;
if(sum > 0) state = '+';
else if(sum < 0) state = '-';
else state ='0';
if(state != S[low][idx]) return false;
}
return true;
}
bool guessMe(int idx){
if(idx == N) return true;
char curState = S[idx][idx];
if(curState == '+'){
for(int i=1; i<=10; i++){
A[idx] = i;
if( isThisRight(idx) && guessMe(idx+1) ) return true;
}
}
else if(curState == '-'){
for(int i=-1; i>=-10; i--){
A[idx] = i;
if( isThisRight(idx) && guessMe(idx+1) ) return true;
}
}
else {
A[idx] = 0;
return guessMe(idx+1);
}
return false;
}
int main()
{
int strIdx=0;
string str;
cin >> N >> str;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(i>j){
S[i][j] = 'X';
continue;
}
S[i][j] = str[strIdx++];
}
}
guessMe(0);
for(int i=0; i<N; i++){
cout << A[i] << ' ';
}
return 0;
}
