pushback

두 가지 방법이 있다.

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때문에 메모리는 두 배정도 더 사용하지만, 매우 만족스러운 속도가 나왔다.