백준 22251번 - 빌런 호석
문제 풀이
괜히 어렵게 생각해서 훨씬 간단히 풀 수 있는 문제를 어렵게 풀었다.
출제자가 권장하는 풀이방법과 아이디어는 거의 비슷하지만, 먼저 입력 숫자들을 쪼개서 백트래킹 형식으로 푸는 방법을 택했지만 상당히 코드가 지저분해지고 복잡해졌다.
핵심은 숫자 0, 1, 2, 3, 4, 5, 6, 7, 8, 9를 디스플레이에 표현했을 때 각 led가 점등되어있는지 아닌지를 배열로 표현해주고, 그것을 사용해서 현재 숫자와 어떤 숫자의 led에는 몇개의 차이가 있는지 구하는 함수를 만들어주면 간단히 풀 수 있다.
문제 링크
소스코드
작성자 코드
#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++;
}
}
Author And Source
이 문제에 관하여(백준 22251번 - 빌런 호석), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@pjh612/백준-22251번-빌런-호석저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)