문제 링크 : https://code.google.com/codejam/contest/6254486/dashboard#s=p2
코드잼 세번째 문제지만, 다른 친구들이 다들 여기서 막히는걸 보고 그냥 D번부터 풀었어서 이 문제는 가장 마지막으로 풀었다. 가장 시간 투자가 적은 문제라 그런지 (끝나고 치킨먹기로 해서..) 그냥 직관적인 로직 그대로 짜서 small set은 풀었는데 large set은 못 풀었다.
문제 요약
한줄요약 : J길이의 잼코인(jamcoin)과, 잼코인 하나당 각 진수(base)에 대한 고유 약수(non-trivial divisor) 9개씩을 N개 만드는 프로그램을 만들어라.
여기에서 잼코인이란 다음과 같은 속성을 만족하는 숫자열인데,
- 모든 숫자들은 0이나 1이어야함.
- 첫번째와 마지막 숫자는 1이어야함.
- 그 숫자열을 2,3,4…10진수로 각각 해석했을때, 전부 소수(prime)가 아니어야함.
문제에 있는 예시를 그대로 베껴오자면, 101은 2진수로 해석하면 소수가 나오기 때문에 (5가 나온다) 잼코인이 아니다. 1001은 잼코인인데, 이진수에서 십진수까지 해석했을때 각각 9, 28, 65, 126, 217, 344, 513, 730, 1001이고 얘네들은 전부 소수가 아니기 때문에 그렇다.
내 풀이
잼코인 제네레이터를 만들라는 문제인데, 내 솔루션은 바로 생각나는대로 코드를 짜서 되게 간단하다. 2번 규칙에 따라 맨 첫,뒷번째 숫자는 무조건 1이 되어야 하니까 그 둘을 제외한 나머지 비트들을(N-2개) 0부터 2^(N-2)까지 for문 돌아가면서, 2-10 진수로 각각 해석(toBase())해보고, 그게 소수인지 아닌지 판단한다.(isPrime())
#include <iostream>
#include <cstdint>
#include <vector>
#include <cmath>
using namespace std;
typedef uint64_t u64;
u64 isPrime(u64 n) {
u64 sqrn = sqrtl(n);
for (int i = 2; i <= sqrn; i++) {
if (n % i == 0) {
return i;
}
}
return false;
}
u64 toBase(vector<bool> jamcoin, int base) {
int ret = 0;
int i = 0;
for (vector<bool>::reverse_iterator rit = jamcoin.rbegin(); rit != jamcoin.rend(); ++rit) {
if (*(rit)) {
ret += pow(base, i);
}
i++;
}
return ret;
}
int main() {
int T; // t for test cases
cin >> T;
for (int count = 1; count <= T; count++) {
// N : length
// J : number of jamcoins
int N, J;
cin >> N >> J;
int jamcoinCount = 0;
// 0 ~ 2^(N-2)
for (u64 i = 0; i < powl(2, N-2); i++) {
vector<bool> jamcoin;
// fill `i` into the jamcoin vector
for (int j = 0; j < N-2; j++) {
jamcoin.insert(jamcoin.begin(), ((i >> j) & 1) != 0);
}
// insert the first, and last digit
jamcoin.insert(jamcoin.begin(), true);
jamcoin.push_back(true);
// check if the jamcoin is valid
vector<u64> divisors;
bool noJamcoin = false; // 'not' jamcoin?
for (int i = 2; i <= 10; i++) {
u64 based = toBase(jamcoin, i);
u64 divisor = isPrime(based);
if (divisor != false) {
divisors.push_back(divisor);
} else {
noJamcoin = true;
break;
}
}
// pruning
if (noJamcoin) {
continue;
}
jamcoinCount += 1;
// print
for (bool b : jamcoin) {
cout << b ? 1 : 0;
}
for (u64 divisor : divisors) {
cout << ' ' << divisor;
}
cout << endl;
if (jamcoinCount >= J)
break;
}
}
return 0;
}
사실 이렇게 짜라고 낸 문제는 아닐텐데… 하면서 문제가 되는 점을 간단하게 생각해보자면 하나의 잼코인을 만들때 들어가는 루프가 진수 변환에서나 소수 검사에서 너무 많은것 같고, 가망이 안 보이는 숫자를 빠르게 쳐내거나, 될만한 숫자들을 우선적으로 검사를 하는 방법들로 돌아가는 시간을 줄였어야 한다고 생각한다. large dataset에서의 최악의 경우는 32길이의 잼코인을 500개 구해야 하는데, 이 경우엔 정말 엄청 많은 시간이 들어갈듯.
맞는 풀이
공식 해설 : https://code.google.com/codejam/contest/6254486/dashboard#s=a&a=2
구글 공식 해설에서 제시한 방법은 간단히 말하자면 ‘될만한 숫자들을 때려 맞추는 방법’ 이라고 할 수 있을것 같다. 그 전에 일단 저 위의 엉성한 코드로 풀었던 small set의 input output을 먼저 보고 시작하도록 하자.
Input
1
16 50
Output
Case #1: 1000000000000001 3 2 5 2 7 2 3 2 7 1000000000000111 3 2 5 2 7 2 3 2 11 1000000000001001 5 5 3 19 17 3 313 19 3 1000000000001101 3 2 5 2 7 2 3 2 11 1000000000010001 37 1009 3 11 107 3 5 463 3 1000000000010011 3 2 5 2 7 2 3 2 7 1000000000011001 3 2 5 2 7 2 3 2 11 1000000000011111 3 2 3 2 7 2 3 2 3 1000000000100101 3 2 5 2 7 2 3 2 7 1000000000101011 3 7 11 3 5 43 3 73 7 1000000000101111 5 2 3 2 17 2 5 2 3 1000000000110001 3 2 5 2 7 2 3 2 11 1000000000110111 3 2 3 2 7 2 3 2 3 1000000000111011 17 2 3 2 29 2 11 2 3 1000000000111101 3 2 3 2 7 2 3 2 3 1000000001000011 3 2 5 2 7 2 3 2 11 1000000001000101 67 2 7 2 2083 2 557 2 107 1000000001001001 3 2 5 2 7 2 3 2 7 1000000001001111 3 2 3 2 7 2 3 2 3 1000000001010001 7 2 59 2 73 2 137 2 1163 1000000001010101 3 7 13 3 5 17 3 53 7 1000000001010111 5 2 3 2 37 2 5 2 3 1000000001011011 3 2 3 2 7 2 3 2 3 1000000001011101 17 2 3 2 1297 2 17 2 3 1000000001011111 7 113 2129 157 131 1399 7 43 241 1000000001100001 3 2 5 2 7 2 3 2 11 1000000001100101 7 97 5807 11 5 13 730157 6523091 8344169 1000000001100111 3 2 3 2 7 2 3 2 3 1000000001101011 5 2 3 2 37 2 5 2 3 1000000001101101 3 2 3 2 7 2 3 2 3 1000000001110011 3 2 3 2 7 2 3 2 3 1000000001110101 5 2 3 2 37 2 5 2 3 1000000001111001 3 2 3 2 7 2 3 2 3 1000000001111101 127 19 7 17 55987 23 7 7 23 1000000001111111 3 2 5 2 7 2 3 2 7 1000000010000101 3 2 5 2 7 2 3 2 11 1000000010001001 7 2 29153 2 13 2 5 2 7187 1000000010001011 3 5 7 3 5 67 3 7 401 1000000010001111 103 2 3 2 383 2 827 2 3 1000000010010001 3 2 5 2 7 2 3 2 7 1000000010010011 7 17 467 23 5 5 5 467 47 1000000010010111 3 2 3 2 7 2 3 2 3 1000000010011001 13 1667 7 13 5 11 11 7 239417 1000000010011011 73 2 3 2 11 2 2969 2 3 1000000010011101 3 2 3 2 7 2 3 2 3 1000000010100001 79 2 89 2 349 2 107 2 359 1000000010100111 5 2 3 2 37 2 5 2 3 1000000010101001 3 5 13 3 5 43 3 73 7 1000000010101011 31 2 3 2 23 2 137849 2 3 1000000010101111 3 79 31 3 431 31 3 2405987 31
output을 우리가 가진 사람의 눈으로 대충 훑어보면 신기한 패턴을 볼 수 있는데, 웃기게도 같은 고유 약수 패턴을 가진 잼코인들이 그래도 꽤나 많이 있다. 3 2 3 2 7 2 3 2 3 이나 3 2 5 2 7 2 3 2 11도 있고 3 2 5 2 7 2 3 2 7 도 종종 눈에 보인다. 한 눈에 보기 좋은 테이블로 모아서 보자면
| base | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| non-trivial divisor | 3 | 2 | 3 | 2 | 7 | 2 | 3 | 2 | 3 |
| 3 | 2 | 5 | 2 | 7 | 2 | 3 | 2 | 11 | |
| 3 | 2 | 5 | 2 | 7 | 2 | 3 | 2 | 7 |
base가 4, 6, 10 일때 고유 약수가 5, 7, 11인 경우가 힌트다. 잘 보면 고유 약수가 각 base보다 1이 많은 경우가 있다. 두번째 리스트 같은 경우에는 아예 base+1의 제일 작은 소인수(prime factor)가 고유 약수로 들어 차 있는걸 알 수 있다. 그럼 이 base+1들을 약수로 가지는 잼코인을 역으로 찾아내면 훨씬 빠르겠지?
이제부턴 특정 진수를 정해놓고 생각하지말고 좀 더 범용적으로 생각해보자. base의 실제 값과는 상관없이 base+1을 b진수로 나타내자면 항상 11(b)다. 여기까지 놓고 봤을때, 11(b)에 어떤 적절한 길이의 0,1로 이루어진 숫자열(b)을 곱해서 우리가 원하는 길이의 잼코인(b)을 구할수 있을것이다. 지금 생각해보니 어떤 적절한 길이의 숫자열도 찾자면 찾을 수 있겠으나… 나눗셈 규칙이 함께 하면 바로 원하는 길이의 잼코인으로 도달할 수 있다.
나눗셈 규칙에 따르면, 0,1로 이루어진 어떤 숫자열중에 11로 나눠지는 숫자는 ‘맨 앞과 맨 뒷 숫자가 1이어야 하고, 숫자열의 홀수번째와 짝수번째 요소중에 1의 갯수가 같아야 한다’라고 한다. 예를들어 11011숫자열을 생각해보자. 위에서 이야기 하는 앞,뒤에 1이 들어와 있고, 짝수번째에 있는 1의 갯수와 홀수번째에 있는 1의 갯수가 같으면서 11011(b) = 1001(b) * 11(b)로 11로 나눠지는 숫자가 된다. 다른 예로는 마찬가지로 1100110011(b) = 10010001(b) * 11(b)로 규칙을 만족하면서 11로 나눠지는 숫자가 된다. 이 11로 나눠지는 조건을 만족하는 잼코인에 대한 정규표현식은 11(0|11)*11이 된다.
위 규칙을 좀 더 일반화 하자면, 어떤 0,1로 이루어진 숫자열이 있을때 그 숫자열을 반복하면서 중간에 0을 맘대로 몇개든 끼워 넣든간에 상관없이, 최종 숫자열은 잼코인이다. 예를들어 어떤 숫자열이 11101이라고 했을때, 어떤 진수 b에 대해서 1110100011101011101(b)는 11101(b)로 나눠질 수 있다. 위의 경우에는 그 ‘어떤 숫자열’이 11인 케이스라고 생각하면 되고.
그래서
이런식으로 잼코인을 역으로 만들어 내는 규칙을 발견했어야 했는데 (그게 문제의 핵심이기도 하고) 그러질 못해서 아쉽다. 직접 최종 솔루션까지 푼 문제가 아니다 보니까 구글 해설을 막 가져다 옮겨놓은것 같네.
그래도 그나마 내 손으로 풀었던 마지막 문제는 역시 나중에…
'프로그래밍' 카테고리의 다른 글
| C#의 람다 변수 캡쳐 (0) | 2017.05.29 |
|---|---|
| Code jam 2016 quals round (D, Fractiles) (0) | 2016.11.11 |
| Code jam 2016 qualification round A, B (0) | 2016.11.02 |
| Cost Amortization (0) | 2016.10.30 |
| Advanced GIT 발표자료 (0) | 2016.08.13 |