[ 백준 1248 ] 맞춰봐 (C++)

백준의 맞춰봐(1248) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 먼저, 문제를 읽고 구해야 하는 값이 무엇인지, 예제입력이 의미하는 것이 무엇인지부터 확실하게 알아보고 가자.

   예제입력을 한번 봐보자.

    -+0++++--+ 이고 출력이 [ -2 , 5 , 3, 1 ] 이다.

   그럼 입력부터 알아보자. 문제에서 "A[i]부터 A[j]까지의 합이 0보다 크면 +, 작으면 -, 0이면 0" 을 적어놨다고 했다.

   즉, 예제입력에서 가장 앞에 '-'가 의미하는 것은 A[0]부터 A[0] 까지 모두 더한 값이 음수입니다를 의미한다.

   실제로 예제 출력을 보면 [ -2, 5, 3, 1 ] 이 있고, 이 때, A[0]부터 A[0]까지 더하게 되면 -2로 음수가 된다.

   그 다음은 '+' 이다. 이 '+'가 의미하는 것은 A[0]부터 A[1]까지 더하면 양수가 나옵니다를 의미한다.

   실제로 예제 출력에서 A[0]부터 A[1]까지 더해보면 -2 + 5 > 0 으로 양수가 나오게 된다.

   이런식으로, A[0] ~ A[N - 1] 까지, A[1] ~ A[N - 1]까지, A[2] ~ A[N -1] , A[N - 1] ~ A[N-1]까지의

   결과를 입력으로 준 것이다.

   그럼 문제를 정말 간단하게 말하자면 다음과 같이 말할 수 있다.

   "-10부터 10까지 총 21개의 숫자가 있습니다. 이 중에서 입력의 조건을 만족하는, N개의 수열을 아무거나 뽑아서

    출력하세요 !"

2) 본인은 그래서 중복순열을 구현하였다. 먼저, 순서에 따라서 결과가 달라질 수 있기 때문에 조합이 아닌 순열을 구현하였고,

   문제에서 같은 숫자를 다시 뽑지 않는다는 조건이 없었기에 중복 순열로 구현을 해 주었다.

   중복순열을 아직 모른다면 아래의 글을 읽고 오도록 하자.

   [ 중복순열 구현하는 법(Click) ]

  

   중복순열을 구현하면서 중간중간 조건에 만족하는지 체크를 해 주었다.

   기존에 뽑은 숫자들과, 지금 현 시점에서 뽑은 숫자들을 모두 더해가면서 입력의 조건을 만족하는 숫자인지 체크해주면서

   뽑는 과정을 진행해 주었다.

  

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 10
using namespace std;
 
int N;
char Res[MAX][MAX];
int Select[MAX];
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = i; j < N; j++)
        {
            cin >> Res[i][j];
        }
    }
}
 
bool Check(int Idx)
{
    int Sum = 0;
    for (int i = Idx; i >= 0; i--)
    {
        Sum = Sum + Select[i];
        if (Res[i][Idx] == '+' && Sum <= 0) return false;
        if (Res[i][Idx] == '-' && Sum >= 0) return false;
        if (Res[i][Idx] == '0' && Sum != 0) return false;
    }
    return true;
}
 
void DFS(int Cnt)
{
    if (Cnt == N)
    {
        for (int i = 0; i < Cnt; i++)
        {
            cout << Select[i] << " ";
        }
        cout << endl;
        exit(0);
    }
 
    for (int i = -10; i <= 10; i++)
    {
        Select[Cnt] = i;
        if (Check(Cnt) == true) DFS(Cnt + 1);
    }
}
 
void Solution()
{
    DFS(0);
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
 
    return 0;
}