두 가지 방법이 있다.
1. 666부터 1씩 증가시키면서 666이 포함되어있는 수인지 확인하는 방법.
2. 666에 앞뒤로 0~9까지 숫자를 붙여가면서 찾는 방법. (= 내가 생각하는 정해)
첫번째 방법은 666이 포함된 수를 오름차순으로 찾을 수 있기 때문에 편하지만, 666이 포함되었는지 확인하는 방법이 조금은 난감하다.
여기서 다시 두 가지로 나눌 수 있다.
1-1. to_string를 이용하여 숫자를 string으로 변환한 다음, string.find를 이용하여 "666"이란 문자열을 포함하는지 확인하는 방법.
1-2. 나머지 연산으로 1의 자리에서부터 3자리씩 보면서 666인지 확인하는 방법이다.
1-1)코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
int cnt = 0, ans = 0;
for (int i = 666; cnt < n; i++) {
string str = to_string(i);
if(str.find("666", 0, 3) != string::npos){
cnt++;
ans = i;
}
}
cout << ans;
return 0;
}코드 자체는 간결하지만 string을 사용하기 때문에 cost가 꽤나 크다.
1-2 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 2147483647;
const int MAX = 10e+8;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
int cnt = 0, ans = 0;
for (int i = 666; cnt < n; i++) {
int num = i;
// 뒤에서부터 3자리씩 보면서 666을 포함하는지 확인
while (num) {
int left = num % 1000;
if (left == 666) {
cnt++;
ans = i;
break;
}
num /= 10;
}
}
cout << ans;
return 0;
}연산을 통해 666이 있는지 확인하기 때문에 1-1방법에 비해 비약적으로 속도를 줄일 수 있다.
두번째 방법은 쉽지만 어렵다. 정확히 말하면 개념은 쉽지만 구현이 살짝 어지럽다. WHY ?
666 앞뒤에 0~9까지 숫자를 붙여보자.
앞 0666, 1666, 2666, 3666, 4666, 5666, 6666, 7666, 8666, 9666
뒤 6660, 6661, 6662, 6663, 6664, 6665, 6666, 6667, 6668, 6669
두 개의 문제점을 확인할 수 있다.
하나) 6666이라는 중복 수가 생긴다. - 이건 의심의 여지가 없는 문제점이다.
둘) int형 변수에 0666은 666으로 저장된다. - 이건 왜 ? 0666을 무시하는 순간 우리는 10666을 평생 만들 수 없다.
중복 수는 해결하기 쉽지만 두번째 문제는 ... 이게 뭘까싶다. 해결하기위해 우리가 0666을 무시했을 때 만들지 못하는 숫자들을 관찰해보자.
5자리 수 : 10666, 20666, 30666, ... 90666
6자리 수 : 100666, 101666, 102666, ... , 200666, ...
이런 숫자들이다. (사실 110666도 못만드는 숫자지만, 10666을 만들 수 있다면 110666은 자동적으로 추가되는 숫자라 제외했다.)
자세히 보자.
5자리 수 : 10666, 20666, 30666, ... 90666
6자리 수 : 100666, 101666, 102666, ... , 200666, ...
관찰 결과 : \(n\)자리 수를 만들려고 할 때, 이미 만들어진 모든 수에 \( 1\times10^{n - 1}, ... , 9\times10^{n - 1}\)를 더해주자.
따라서 666을 포함한 n자리의 수를 만드는 방법은,
1. 이미 만들어진 모든 수에 \( 1\times10^{n - 1}, ... , 9\times10^{n - 1}\)를 더한 수
2. 666을 포함한 n - 1자리의 수 앞에 0~9을 추가한 수
3. 666을 포함한 n - 1자리의 수 뒤에 1~9을 추가한 수
4. 중복 수 제거이다.
살짝 최적화를 해본다면, 2번에서 만들어지는 모든 수는 이미 1번에서 만들어져 있기 때문에 1, 3, 4만 진행하면 된다.
최적화를 조금 더 해본다면, set를 쓴다면 중복 수는 자동적으로 무시되기 때문에 1, 3만 진행하면 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 2147483647;
const int MAX = 10e+8;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
// 10,000번째 수까지만 보기 때문에 7자리의 수들까지만 봐도 충분하다.
set<int> num[8]; // num[i]에는 666을 포함한 i자리 수들을 저장하고 있다.
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
int cnt = 1;
num[3].insert(666);
for (int i = 4; i < 8 && cnt < n; ++i) {
int pos = (int)pow(10, i - 1);
// 앞에 추가
for(int from = 3; from < i; ++from)
for (int prev : num[from])
for (int j = 1; j < 10; ++j)
num[i].insert(j * pos + prev);
// 뒤에 추가
for (int prev : num[i - 1]) for (int j = 0; j < 10; ++j) num[i].insert(prev * 10 + j);
cnt += num[i].size();
}
for (int i = 3; i < 8; ++i) {
if (n > num[i].size()) n -= num[i].size();
else {
// set는 index접근이 불가능하기 때문에 iterator를 사용
set<int>::iterator it = num[i].begin();
for (int i = 1; i < n; ++i) ++it;
cout << *it;
break;
}
}
return 0;
}set때문에 메모리는 두 배정도 더 사용하지만, 매우 만족스러운 속도가 나왔다.
'BOJ_단계별로 풀어보기(9단계~) > [10단계] 브루트 포스' 카테고리의 다른 글
| [백준 1018] 체스판 다시 칠하기 (0) | 2022.03.03 |
|---|---|
| [백준 7568] 덩치 (0) | 2022.03.03 |
| [백준 2231] 분해합 (0) | 2022.03.03 |
| [백준 2798] 블랙잭 (0) | 2022.03.02 |