[BOJ 24441 // C++] 행운 수 판정

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 24441번 문제인 행운 수 판정이다.

문제는 아래 링크를 확인하자.

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

24441번: 행운 수 판정

문제에서 주어지는 수가 Lucky number인지 아닌지를 판별하는 문제이다.

 

n의 범위가 그리 크지 않으므로(100만) 느리더라도 쉽고 단순한 방법으로 100만 이하의 lucky number를 저장한 배열을 미리 계산해낸 후 그 배열을 이용한 코드를 제출하는 것으로 문제를 해결할 수 있다.

 

단, boj에 제출할 수 있는 코드에는 길이(용량) 제한이 있으므로 자신의 코드가 제출이 안 된다면 배열에 대응되는 문자열을 적절히 압축해 제출하고 코드에서 그 압축을 풀어 사용하는 식으로 구현하자.

 

아래는 제출한 소스코드를 생성하는 코드이다.

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;

int arr[1000001];
string s = "";
string ss = "";
string s1 = "#include <iostream>\n#include <string>\nusing namespace std;\n\nstring ss = \"";
string s2 = "\";\nstring s = \"\";\n\nint main() {\n\tios::sync_with_stdio(0);\n\tcin.tie(0);\n\t\n\tfor (auto l : ss) {\n\t\tif (l == '0') s += \"000\";\n\t\telse if (l == '1') s += \"010\";\n\t\telse s += \"100\";\n\t}\n\t\n\tint T; cin >> T;\n\twhile (T--) {\n\t\tint x; cin >> x;\n\t\tif (s[x] == '1') cout << \"lucky\\n\";\n\t\telse cout << \"unlucky\\n\";\n\t}\n}";

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

	for (int i = 1; i < 1000001; i += 2) arr[i] = 1;
	int CNT = 2, cnt = 0, idx = 0;
	while (cnt < CNT && idx < 1000001) {
		if (arr[idx]) {
			cnt++;
			if (cnt == CNT) break;
		}
		idx++;
	}
	while (idx < 1000001) {
		int tmp = 0;
		bool chk = 1;
		for (int i = 1; i < 1000001; i += 2) {
			if (arr[i]) {
				tmp++;
				if (tmp == idx) {
					arr[i] = 0;
					tmp = 0;
					chk = 0;
				}
			}
		}
		if (chk) break;
		CNT++;
		cnt = 0, idx = 0;
		while (cnt < CNT && idx < 1000001) {
			if (arr[idx]) {
				cnt++;
				if (cnt == CNT) break;
			}
			idx++;
		}
	}
	for (int i = 0; i < 1000001; i++) {
		s += to_string(arr[i]);
	}

	s += "0";

	for (int i = 0; i < 1000002; i += 3) {
		if (s.substr(i, 3) == "000") ss += "0";
		else if (s.substr(i, 3) == "010") ss += "1";
		else ss += "2";
	}

	ofstream wf;
	wf.open("ans.txt");
	wf.write(s1.c_str(), s1.size());
	wf.write(ss.c_str(), ss.size());
	wf.write(s2.c_str(), s2.size());
	wf.close();
}