백준 1248 맞춰봐

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

1248번: 맞춰봐

문제의 본문을 읽으면서 문제를 장난으로 냈나? 생각할 정도로 이전에 문제와는 대화형이 많은 내용이였다 결국은 

위의 80%정도가 대화였고 나머지 20 %정도가 실제 문제 풀이를 위한 설명이였던것 같습니다.

결론적으로 

입력을 보면

4

- + 0 + + + + - - + 

주어지는데 

 

1 2 3 4

0 5 6 7

0 0 8 9

0 0 0 10

저렇게 입력이 4가 들어오는 경우 이차원 배열에 

4개의 수의 합이 들어가게 되는데 

출력을 보면 

Arr 배열 

Arr[0] = -2, Arr[1] = 5, Arr[2] = -3, Arr[3] = 1 

이라면 

예를 들어 0,2라면 Arr[0]+ Arr[1] + Arr[2] 를 더한다는 의미 이므로 아래와 같이

배열 0, 0 은 1번에 더해지는 것으로   Arr[0] 인                        -2 = -2             이므로 - 가 되고

배열 0, 1 은 2번에 더해지는 것으로   Arr[0] + Arr[1]                 -2 + 5 = 3        이므로 + 가되고

배열 0, 2 는 3번에 더해지는 것으로   Arr[0] + Arr[1] + Arr[2]      -2 + 5 + -3 = 0 이므로 0 이 됩니다.

 

배열 1, 1 은 4번에 더해지는 것으로   Arr[1] 인                         5 = 5              이므로 + 가 됩니다.

이런식으로 

각 이차원 배열의 y와x가 있을때 y 부터 x 까지 의 숫자를 인덱스로 가지는 배열의 합이 들어가는 것 입니다.

그렇게 처음에 저는 구현할때 입력을 받고 위의 이차원 배열에 입력으로 주어지는 - + 0 을 먼저 넣었습니다.

 

그리고 나서 재귀를 이용하여 백트래킹을 하였습니다. 

이유는 -10 ~ 0 ~ 10 까지 주어진 수였고 그것이 겹치는것이 없이 모든 경우를 보기 위해서 선택했습니다.

 

설명이 길어진것 같은데 그냥 단순히 N 4라면 4개의 배열에 숫자를 전부 다 넣어보면 시간초과가 날수 있기때문에

배열에 숫자를 넣기전에 chk() 함수를 구현하여 위의 계산식에 근거하여 0번배열에는 -값이 들어갈수 있도록 하여

경우를 줄여서 시간초과를 해결했습니다.

 

익숙해진다고 생각을 했던 백트래킹이였지만 아직까지도 조금 한부분이 아직 완벽히 채워지지 않아서

실망스러웠지만 앞으로는 실수하지 않도록 할것이라고 다짐했습니다.

 

아래 소스를 보시고 이해를 하시면 더 쉽습니다.

#include<stdio.h>
#include<stdlib.h>
int N;
int ret;
int num[10];
char result[56];
char cc[56][56] = { 0, };
bool chk(int idx) {
    int cdx = 0;
    int sum = 0;
    for (int i = 0; i <= idx; i++) {
        int sum = 0;
        for (int j = i; j <= idx; j++) {
            sum += num[j];
            char a;
            if (sum < 0)a = '-';
            if (sum == 0)a = '0';
            if (sum > 0)a = '+';
            if (a != cc[i][j]) {
                return 0;
            }
        }
    }
    return 1;
}
void dfs(int idx) {
    if (idx == N) {
        int cdx = 0;
        //if (chk(N-1) == 0) return;
        for (int i = 0; i < N; i++) {
            printf("%d ", num[i]);
        }
        //printf("\n");
        //return;
        exit(0);
    }
    //chk(idx);// 가지치기
    for (int y = -10; y <= 10; y++) {
        num[idx] = y;
        if (chk(idx)) {
            dfs(idx + 1);
        }
        num[idx] = 0;
    }
}
 
int main(void)
{
    scanf("%d", &N);
    scanf("%s", result);
    int idx = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i; j < N; j++) {
            cc[i][j] = result[idx++];
        }
    }
    dfs(0);
    return 0;
}

오늘은 여기까지이고 항상 모든 경우를 보려고 하지말고 가지를 칠것을 치도록 해야한다는 것을 배우게 되었고 

여러가지로 접근하는법이 많구나 느꼈습니다.

보시느라 고생 많으셨습니다. 감사합니다.