[BOJ]1248번: 맞춰봐 (c++)

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

1248번: 맞춰봐

 

 

#include <iostream>
#include <vector>

using namespace std;

// 숫자가 부호와 일치하는지 확인
bool inline sign_check(int num, int sign)
{
	if (sign == 0)
	{
		return num == 0;
	}
	else
	{
		return num * sign > 0;
	}
}

// 새로 들어올 숫자가 구간별 부호 조건에 일치하는지 확인
bool check(vector<vector<int>> &sign, vector<int> &numbers, int target, int depth)
{
	int sum = target;
	for (int i = depth - 1; i >= 0; --i)
	{
		// i ~ depth 자리까지의 합이 부호 조건에 일치하는지 확인
		sum += numbers[i];
		if (!sign_check(sum, sign[i][depth]))
		{
			return false;
		}
	}
	return true;
}

bool go(vector<vector<int>> &sign, vector<int> &numbers, int N, int depth)
{
	// 숫자가 모두 조합되면 출력
	if (depth == N)
	{
		for (int i = 0; i < N; ++i)
		{
			cout << numbers[i] << ' ';
		}
		cout << '\n';
		return true;
	}

	// 부호가 0일 때
	if (sign[depth][depth] == 0)
	{
		numbers[depth] = 0;
		return go(sign, numbers, N, depth + 1);
	}

	// 부호가 0보다 크거나 작을때
	for (int i = 1; i <= 10; ++i)
	{
		// 새로 들어올 숫자에 부호 반영
		int target = i * sign[depth][depth];
		
		// 새로 들어올 숫자가 구간별 부호 조건에 일치하는지 확인
		if (check(sign, numbers, target, depth))
		{
			numbers[depth] = target;

			// 한번이라도 조합이 완성되어 출력되면 종료
			if (go(sign, numbers, N, depth + 1))
			{
				return true;
			}
		}
	}
	return false;
}

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

	// 입력
	int N;
	cin >> N;
	string s;
	cin >> s;

	// -, 0, + 부호를 -1, 0, 1 로 변환하여 벡터 저장
	vector<vector<int>> sign(N, vector<int>(N));
	int idx = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = i; j < N; ++j)
		{
			if (s[idx] == '0')
			{
				sign[i][j] = 0;
			}
			else if (s[idx] == '+')
			{
				sign[i][j] = 1;
			}
			else 
			{
				sign[i][j] = -1;
			}
			++idx;
		}
	}

	// 백트랙킹 - 숫자 조합
	vector<int> numbers(N);
	go(sign, numbers, N, 0);

	return 0;
}

 

 

TIP

조건 검사를 두려워하지 말라...

문제에서 체크해야할 조건이 많다면 많은대로 그냥 다 검사하면 된다

 

검사 경우의 수를 줄이는건 기본틀을 짜고 난 다음에 생각할 일이다.

물론 첨부터 아이디어가 나면 더 좋고ㅋㅋ

 

나는 자꾸 코드가 길어지면 겁을 먹는 경향이 있는데,

풀고나면 매우 쓸데 없는 걱정이다. 

기본 전략을 세우고 틀이 되는 코드를 짜는게 제일 중요하다. 

 

 

흐름은 다음과 같다. 

 

1. 백트랙킹 문제임을 파악

아래처럼 dfs함수, 종료조건, 조합코드(?) 까지 기본 코드를 먼저 쓰고 나면 머리속이 좀더 간단해진다. 

bool go(vector<vector<int>> &sign, vector<int> &numbers, int N, int depth)
{
    // 종료 조건
    if (depth == N)
    {
        // 출력
        return true;
    }

    // 일단 주어진 범위만큼 숫자 조합해보기
    for (int i = -10; i <= 10; ++i)
    {
        // 조건에 맞는지 확인하기
        if (check())
        {
            numbers[depth] = i;

            // 재귀호출
          	go(sign, numbers, N, depth + 1));
        }
    }
    return false;
}

 

 

2. 조건을 판별하는 함수를 작성해준다. 

세부 구현은 위 코드 참고..

 

 

3. 이제 검사 경우의 수를 줄일 궁리를 한다.

S[i][i] 가 0인 경우, i번째 자리 숫자는 0밖에 될 수 없다 --> S[i][i] 가 0인 경우 분리하기

S[i][j] 가 음수면 어차피 -10~-1 내에서 골라야 하고,

양수면 어차피 1 ~ 10에서 골라야 한다 --> 부호에 따라 분리하기

bool go(vector<vector<int>> &sign, vector<int> &numbers, int N, int depth)
{
    ...

    // 부호가 0일 때
    if (sign[depth][depth] == 0)
    {
        numbers[depth] = 0;
        return go(sign, numbers, N, depth + 1);
    }

    // 부호가 0보다 크거나 작을때
    for (int i = 1; i <= 10; ++i)
    {
        // 새로 들어올 숫자에 부호 반영
        int target = i * sign[depth][depth];
        
        // 새로 들어올 숫자가 구간별 부호 조건에 일치하는지 확인
        if (check(sign, numbers, target, depth))
        {
 
    ...
}

 

 

너무 처음부터 모든 것을 고려하고 코드를 짜려면 머릿속이 꼬이기만 한다.

한스텝 한스텝 천천히 짜자.