문제 풀이

괜히 어렵게 생각해서 훨씬 간단히 풀 수 있는 문제를 어렵게 풀었다.
출제자가 권장하는 풀이방법과 아이디어는 거의 비슷하지만, 먼저 입력 숫자들을 쪼개서 백트래킹 형식으로 푸는 방법을 택했지만 상당히 코드가 지저분해지고 복잡해졌다.

핵심은 숫자 0, 1, 2, 3, 4, 5, 6, 7, 8, 9를 디스플레이에 표현했을 때 각 led가 점등되어있는지 아닌지를 배열로 표현해주고, 그것을 사용해서 현재 숫자와 어떤 숫자의 led에는 몇개의 차이가 있는지 구하는 함수를 만들어주면 간단히 풀 수 있다.

문제 링크

boj/22251

소스코드

PS/22251.cpp

작성자 코드

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include<algorithm>
#include<memory.h>
using namespace std;

int num[10][9] =
{
	 { 1,1,1,1,1,1,0 },
	{0,1,1,0,0,0,0},
	{1,1,0,1,1,0,1},
	{1,1,1,1,0,0,1}
	,{0,1,1,0,0,1,1}
	,{1,0,1,1,0,1,1}
	,{1,0,1,1,1,1,1}
	,{1,1,1,0,0,0,0}
	,{1,1,1,1,1,1,1}
	,{1,1,1,1,0,1,1}
};

vector<int> v;
vector<int> v2;
int n, k, p, x, x2, n2;
long long ans;
void solution(int idx, int max, int cnt);
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k >> p >> x;
	n2 = n;
	x2 = x;

	for (int i = 0; i < k; i++)
	{
		v.push_back(x % 10);
		x /= 10;
	}
	for (int i = 0; i < k; i++)
	{
		v2.push_back(n % 10);
		n /= 10;
	}
	reverse(v2.begin(), v2.end());
	reverse(v.begin(), v.end());
	solution(0, k, 0);
	cout << ans;
}

int getdiff(int a, int b)
{
	int cnt = 0;
	for (int i = 0; i < 7; i++)
	{
		if (num[a][i] != num[b][i])
			cnt++;
	}
	return cnt;
}

int getnum()
{
	int ret = 0;
	for (int i = 0; i < v.size(); i++)
	{
		ret *= 10;
		ret += v[i];
	}
	return ret;
}

void solution(int idx, int max, int cnt)
{
	if (idx == max)
	{
		if (getnum() > n2 || getnum() == x2)
			return;
		for (int i = 0; i < max; i++)
		{
			if (v[i] != 0)
			{
				ans++;
				return;
			}
		}
		return;
	}

	for (int i = 0; i <= 9; i++)
	{
		if (getdiff(v[idx], i) + cnt <= p)
		{
			int tmp = v[idx];
			v[idx] = i;
			solution(idx + 1, max, cnt + getdiff(tmp, i));
			v[idx] = tmp;
		}
	}
}

출제자 방식 코드

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include<algorithm>
#include<memory.h>
using namespace std;

int num[10][9] =
{
	 { 1,1,1,1,1,1,0 },
	{0,1,1,0,0,0,0},
	{1,1,0,1,1,0,1},
	{1,1,1,1,0,0,1}
	,{0,1,1,0,0,1,1}
	,{1,0,1,1,0,1,1}
	,{1,0,1,1,1,1,1}
	,{1,1,1,0,0,0,0}
	,{1,1,1,1,1,1,1}
	,{1,1,1,1,0,1,1}
};

vector<int> v;
vector<int> v2;
int n, k, p, x;
long long ans;
void solution();
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k >> p >> x;
	solution();
	cout << ans;
}

int getDiffOne(int a, int b)
{
	int cnt = 0;
	for (int i = 0; i < 7; i++)
	{
		if (num[a][i] != num[b][i])
			cnt++;
	}
	return cnt;
}

int getDiff(int x, int y)
{
	int ret = 0;
	for (int i = 0; i < k; i++)
	{
		ret += getDiffOne(x % 10, y % 10);
		x /= 10;
		y /= 10;
	}
	return ret;
}

void solution()
{
	for (int i = 1; i <= n; i++)
	{
		if (i == x)
			continue;
		if (getDiff(i, x) <= p)
			ans++;
	}
}