C++ 1248 Guess

https://www.acmicpc.net/problem/1248

1248번: Guess

틀린 문제이기도 하고 풀면서 배운 점이 있어서 정리하려고 합니다.

 

문제 설명

부호 매트릭스가 주어지고, 해당 부호를 만족시키는 정수 수열을 찾는 문제이다. 가능한 수의 범위는 -10~10으로 정해주었다. 

이해를 돕기 위해 1번 행만 살펴보면,

1행 1열이 -이므로 첫 번째 원소는 음수이다. 

1행 2열이 +이므로 첫 번째 원소와 두 번째 원소를 더한 값은 양수이다.

1행 3열이 0이므로 첫 번째 원소부터 세 번째 원소까지 더한 값은 0이다.

1행 4열이 0이므로 첫 번째 원소부터 네 번째 원소까지 더한 값은 양수이다.

 

처음 생각한 풀이(틀림)

우선 값의 범위가 -10~10로 주어졌으므로 완전탐색을 고려할 수 있다.

1. 매트릭 s의 s[i][i]를 확인하여 i번 째 숫자가 양수인지 음수인지 판단한다.

2. 음수이면 -10~-1, 양수이면 1~10, 0이면 0을 탐색 범위로 잡는다.

3. 위 범위에서 재귀 호출하여 n개의 숫자를 결정한다.

4. 결정한 n개의 숫자가 문제의 조건과 유효한지 판단하고, 유효하면 출력후 종료한다.

 

틀린 코드

#include <bits/stdc++.h>
using namespace std;
int n;
bool vis[21];
char s[11][11];
vector<int> nums;

bool check() {
    for(int i=0; i<n; i++) {
        for(int j=i+1; j<n; j++) {
            int sum = accumulate(nums.begin() + i, nums.begin() + j + 1, 0);
            if(s[i][j] == '-' && sum >= 0) {
                return false;
            }
            else if(s[i][j] == '+' && sum <= 0) {
                return false;
            }
            else if(s[i][j] == '0' && sum != 0) {
                return false;
            }
        }
    }
    return true;
}

void dfs(int k) {
    if(k == n) {
        if(check()) {
            for (const auto &num: nums) {
                cout << num << ' ';
            }
            exit(0);
        }

    }
    int st;
    int en;
    if(s[k][k] == '0') {
        nums.push_back(0);
        dfs(k+1);
    }
    else if(s[k][k] == '+') {
        st = 1;
        en = 10;
    }
    else if(s[k][k] == '-'){
        st = -10;
        en = -1;
    }

    for(int i=st; i<=en; i++) {
        if(vis[i+10]) continue;
        vis[i+10] = true;
        nums.push_back(i);
        dfs(k+1);
        vis[i+10] = false;
        nums.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i=0; i<n; i++)
        for(int j=i; j<n; j++)
            cin >> s[i][j];

    dfs(0);
}

처음에는 n개의 숫자를 모두 확인한 후 check 함수를 호출하여 이게 가능한 케이스인지 확인 하였다. 하지만 이렇게 하니 최악의 경우 10^10의 for문을 반복하므로 시간초과가 발생한다. 

 

처음 풀이에서는 모두 다른 정수여야한다고 착각하고 풀어서 vis로 이미 추가한 숫자인지 확인하는 코드도 제거해주어야 한다.

 

위 풀이에서는 재귀 호출 전 미리 prunning하는 과정으로 수정하였다.

1. 매트릭 s의 s[i][i]를 확인하여 i번 째 숫자가 양수인지 음수인지 판단한다.

2. 음수이면 -10~-1, 양수이면 1~10, 0이면 0을 탐색 범위로 잡는다.

3. 재귀 호출 전 조건에 맞는 경우인지 판단하여 맞다면 반복적으로 재귀 호출하여 최종적으로 n개의 숫자를 결정한다.

4. n개의 숫자가 결정되면 출력후 종료한다. (조건에 맞는 숫자만 선택되므로 검사할 필요가 없다.)

 

기존 코드는 n개의 숫자를 모두 찾은 후 유효한 케이스인지 검사했지만, 위 풀이는 다음 재귀 호출을 하기 전에 조건을 만족하는지 검사하여, 맞지 않는 경우면 더 이상 재귀 호출을 하지 않고 건너뛴다. (재귀 호출 전 prunning)

위와 같이 처음 -10을 선택하고 두 번 째로 1을 선택하기 전에 검사하여 만약 매트릭의 부호 조건을 만족하지 않으면(non-promising) n개를 모두 선택하지 않고 backtrack한다. 

 

맞은 코드

#include <bits/stdc++.h>
using namespace std;
int n;
char s[11][11];
vector<int> nums;

bool check(int idx) {
    for(int i=0; i<idx; i++) {
        int sum = accumulate(nums.begin() + i, nums.begin() + idx + 1, 0);
        if(s[i][idx] == '-' && sum >= 0) {
            return false;
        }
        else if(s[i][idx] == '+' && sum <= 0) {
            return false;
        }
        else if(s[i][idx] == '0' && sum != 0) {
            return false;
        }
    }
    return true;
}

void dfs(int k) {
    if(k == n) {
        for (const auto &num: nums) {
            cout << num << ' ';
        }
        cout << '\n';
        exit(0);
    }

    int st;
    int en;
    if(s[k][k] == '0') {
        nums.push_back(0);
        if(check(k))
            dfs(k+1);
        nums.pop_back();
    }
    else if(s[k][k] == '+') {
        st = 1;
        en = 10;
    }
    else if(s[k][k] == '-'){
        st = -10;
        en = -1;
    }

    for(int i=st; i<=en; i++) {
        nums.push_back(i);
        if(check(k))
            dfs(k+1);
        nums.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i=0; i<n; i++)
        for(int j=i; j<n; j++)
            cin >> s[i][j];

    dfs(0);
}

코드를 보면 vis관련 코드를 제거하고, dfs(k+1) 호출전 check 함수로 for문을 돌며 i번 째부터 현재 추가된 숫자까지 합을 구하여 매트릭 부호를 만족하는지를 검사한다.

예를 들면 1번 째 수~ idx번 째 수의 합, 2번 째 수 ~ idx번 째 수의 합, 3번 째 수 ~ idx 번 째 수의 합 ... 을 구해서, 각각이 부호를 충족하는지 비교한다.