백준 1248번 맞춰봐

문제 링크 : https://www.acmicpc.net/problem/1248

1248번: 맞춰봐

풀이

백트래킹 문제입니다!

이 문제는 서론이 좀 긴데 간단히 압축하자면, -10~10 까지의 정수로 채운 S배열이 있는데,

S[i][j]는 A[i] ~ A[j] 까지의 합의 부호를 나타낸다. 따라서 S배열은 i와 j가 같을 때를 이은 대각선의 오른쪽 위 부분만 채우게된다.(배열은 총 N*(N+1)/2 개의 문자가 있다고 문제에서 주어짐)

따라서 S배열이 주어졌을 때 이를 만족하게끔 A배열을 완성시켜 출력하여야한다.

이 때 수열의 크기 N이 10보다 작거나 같은 자연수이기 때문에 A배열을 -10 ~ 10 까지 모든 경우의 수를 만들어 S배열에 만족하는지 구하려면 총 O(21^N)의 시간 복잡도가 발생하여 구할 수 없게 된다.

 

따라서 백트래킹을 이용하여 시간을 최대한 줄여보고자 한다.

백트래킹을 사용할 수 있는 부분은

 

1. 출력 조건에서 답이 여러가지 일 경우 아무거나 출력하면 되므로 웬만하면 S[i][j]의 부호만 만족시키면 재귀호출을 이용하여 다음으로 넘어갈 수 있다.

 

2. S[i][i] 는 A[i]의 부호와 같다. 따라서 S[i][i]가 0일 때 A[i]는 반드시 0이다. 따라서 0인 경우 확정짓고 넘어갈 수 있다.

 

3. S[i][k] 를 구했을 때 S[i][k+1] 을 구할 때 이미 S[k+1][k+1]에서 구한 A[k+1]의 부호를 통해 -10~-1 또는 1~10 만 봐도 된다.

 

4. A[i] ~ A[k] 까지의 합에 따라 S[i][k+1]의 부호에 맞게 A[k+1]가 맞는지 확인 할 수 있다.

 

이런 과정을 코드에 집어넣어 brute force를 실행하면 시간복잡도를 정말 많이 단축시킬 수 있다! (21가지를 다 볼 필요도 없고, 모든 칸을 다 집어넣지 않아도 결과를 확인할 수 있기 때문이다.)

 

소스 코드

#include <iostream>
#include <string>
using namespace std;
 
int n;
int sign[10][10];
int ans[10];
 
bool check(int idx) { //백트래킹
    int sum = 0;
    for (int i = idx; i >= 0; i--) {
        sum += ans[i];
        if (sign[i][idx] == 0) {
            if (sum != 0) return false;
        }
        else if (sign[i][idx] < 0) {
            if (sum >= 0) return false;
        }
        else if (sign[i][idx] > 0) {
            if (sum <= 0) return false;
        }
    }
    return true;
}
bool go(int idx) { //brute force
    if (idx == n) return true;
    if (sign[idx][idx] == 0) {
        ans[idx] = 0;
        return check(idx) && go(idx + 1);
    }
    for (int i = 1; i <= 10; i++) {
        ans[idx] = sign[idx][idx] * i;
        if (check(idx) && go(idx + 1)) return true;
    }
    return false;
}
int main() {
    scanf("%d", &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++;
        }
        
    }
    go(0);
    for (int i = 0; i < n; i++) {
        cout << ans[i] << ' ';
    }
    cout << "\n";
    return 0;
}

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~