[백준] 1248번 : 맞춰봐

문제

 

---

풀이

 

문제가 참 긴데 사실 마지막 문단을 빼곤 쓸데없는 말이다. 입력값 처리의 벽만 넘으면 아주 못 풀 문제는 아니다.

 

일단 한줄로 들어온 저 input을 예쁘게 정리하면

-	+	0	+
	+	+	+
		-	-
			+

이렇게 된다.

 

S[i][j] = A[i]+A[i+1]+...+A[j]라고 했다.

그럼 S[0][0] = A[i]인 것이고 S[i][i]에는 A[i]의 부호가 있는 것이다.

나름 괜찮은 정보인데 다 풀고보니 난 이 정보를 사용하지 않았다.

 

A[0]부터 A[3]까지의 순서로 값을 구할 것이다.

A[0]은 A[0]<0이라는 조건만 만족하면 된다. (0, 0)

A[1]은 여기에 추가로 A[0]+A[1]>0, A[1]>0이어야 한다. (0, 1), (1, 1)

A[2]은 여기에 또 추가로 A[0]+A[1]+A[2]=0, A[1]+A[2]>0, A[2]<0이어야 한다. (0, 2), (1, 2), (2, 2)

A[3]은 귀찮아서 안쓰겠다.

 

아무튼 이런식으로 -10부터 10까지의 값에 대해 promising 여부를 확인하며 진행하다가 처음으로 가능한 수의 조합을 전부 찾으면 함수를 종료한다.

---

소스코드

 

#include <iostream>
#include <string>

using namespace std;

char cmp[10][10];
int arr[10], N;
bool isFound;

bool isPromising(int cnt, int sum) {
    for (int i = 0; i <= cnt; i++) { //cmp[0][cnt]~cmp[cnt][cnt]까지 열 1개 확인
        if ((cmp[i][cnt] == '+') && (sum <= 0)) //+인데 0보다 작거나 같으면 안됨
            return false;
        else if ((cmp[i][cnt] == '-') && (sum >= 0)) //-인데 0보다 크거나 같으면 안됨
            return false;
        else if ((cmp[i][cnt] == '0') && (sum != 0)) //0인데 0이 아니면 안됨
            return false;
        sum -= arr[i];
    }
    return true;
}

void backtracking(int cnt, int sum) {
    if (cnt == N) { //제일 먼저 찾은 arr
        isFound = true;
        return;
    }
    for (int i = -10; i <= 10 && !isFound; i++) {
        arr[cnt] = i; //arr 배열에 i 입력
        if (isPromising(cnt, sum + i)) //(sum+i)=(arr[0]부터 arr[cnt]까지 더한 값)
            backtracking(cnt + 1, sum + i);
    }
}

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

    string input;

    cin >> N >> input;
    int pos = 0;
    for (int i = 0; i < N; i++) { //string 입력을 행렬로 정리
        for (int j = i; j < N; j++)
            cmp[i][j] = input[pos++];
    }
    backtracking(0, 0);
    for (int i = 0; i < N; i++)
        cout << arr[i] << ' ';
}

전체 소스코드다.

 

    int pos = 0;
    for (int i = 0; i < N; i++) { //string 입력을 행렬로 정리
        for (int j = i; j < N; j++)
            cmp[i][j] = input[pos++];
    }
    backtracking(0, 0);

위 그림처럼 input을 처리하기 위해선 이렇게 코드를 작성하면 된다.

 

void backtracking(int cnt, int sum) {
    if (cnt == N) { //제일 먼저 찾은 arr
        isFound = true;
        return;
    }
    for (int i = -10; i <= 10 && !isFound; i++) {
        arr[cnt] = i; //arr 배열에 i 입력
        if (isPromising(cnt, sum + i)) //(sum+i)=(arr[0]부터 arr[cnt]까지 더한 값)
            backtracking(cnt + 1, sum + i);
    }
}

백트래킹 함수이다. cnt는 현재까지 찾은 숫자의 갯수이고 sum은 A[0]+A[1]+...+A[cnt-1]을 한 값이다.

-10부터 10까지의 범위인 i에 대해 isPromising 함수로 투입가능 여부를 확인하고 백트래킹 함수를 호출한다.

 

bool isPromising(int cnt, int sum) {
    for (int i = 0; i <= cnt; i++) { //cmp[0][cnt]~cmp[cnt][cnt]까지 행 1개 확인
        if ((cmp[i][cnt] == '+') && (sum <= 0)) //+인데 0보다 작거나 같으면 안됨
            return false;
        else if ((cmp[i][cnt] == '-') && (sum >= 0)) //-인데 0보다 크거나 같으면 안됨
            return false;
        else if ((cmp[i][cnt] == '0') && (sum != 0)) //0인데 0이 아니면 안됨
            return false;
        sum -= arr[i];
    }
    return true;
}

cnt=2라고 해보자. 지금 우리는 A[2]에 들어온 값이 promising한 값인지 확인하려는 것이다.

 

-	+	0	+
	+	+	+
		-	-
			+

여기 붉은색으로 표시된 부분을 확인하면 된다.

 

sum=A[0]+A[1]+A[2]이다. A[0]과 A[1]은 이미 promising 검사를 마쳤으니 A[2]만 확인하면 된다.

먼저 sum=0인지 확인한다. 그렇지 않다면 바로 false를 리턴한다.

 

통과했다면 sum에서 A[0]을 뺀다. 그럼 sum=A[1]+A[2]가 된다.

이 값이 양수인지 확인한다. 0보다 작거나 같다면 false를 리턴한다.

 

마지막으로 sum에서 A[1]을 뺀다. 그럼 sum=A[2]가 된다.

이 값이 음수인지 확인한다. 0보다 크거나 같다면 false를 리턴한다.

 

이 모두를 통과했다면 true를 반환한다.