OJUZ balkan11_cmp - https://oj.uz/problem/view/balkan11_cmp

풀이 1 (0점)

가장 먼저 생각하는 방법은 수를 이진수로 메모리의 1 - 12에 저장해 놓는 것이다.

이럴 경우, 수를 저장하는 데 최악의 경우 12번, 수를 비교하는데 최악의 경우 12번 필요하므로,
총 24번 함수를 사용하게 되어 점수를 얻을 수 없다.

코드 1
#include "cmp.h" void remember(int n) { for (int i = 11; i >= 0; --i) { if (n & (1 << i)) bit_set(i + 1); } } int compare(int b) { for (int i = 11; i >= 0; --i) { const int bb = (b >> i) & 1; const int ab = bit_get(i + 1); if (ab > bb) return -1; else if (ab < bb) return +1; } return 0; }
풀이 2 (46점)

저장하는 방법을 약간 바꾸자. 완전 이진 트리 중, leaf 노드의 수가 4096개인 노드를 생각해보자.

이를 배열로 표현한다면 다음과 같이 표현할 수 있다.

  • 1번 메모리는 Root
  • 2 - 3번 메모리는 Root의 왼쪽, 오른쪽 자식
  • ...
  • 4096 - 8191번 메모리는 Leaf 노드

이 때, 아래의 우리가 저장해야하는 수가 아래의 4096개의 노드 중 하나라고 생각하고, 해당 노드로부터 루트로 가는데 거치는 노드를 모두 1로 저장해 놓자.
이러면 총 13번의 bit_set 호출이 필요하다.

이제 수를 비교할 때는, 아래 있는 두 노드가 들어와서 LCA를 찾고, 누가 오른쪽 자식인지(더 큰지)를 확인하는 것과 똑같다고 할 수 있다.

트리의 높이는 13이므로, 이분 탐색을 할 때 4번의 탐색이 필요하다.
실제로는 루트에 bit_set을 할 필요는 없기 때문에, 총 16번 호출로 가능하다.

코드 2
#include "cmp.h" void remember(int n) { int nowp = 1; for (int i = 11; i >= 0; --i) { if (n & (1 << i)) nowp = nowp * 2 + 1; else nowp = nowp * 2; bit_set(nowp); } } int compare(int b) { int same = 0, l = 1, r = 12; while (l <= r) { const int m = (l + r) / 2; const int c = (b >> (12 - m)) | (1 << m); if (bit_get(c)) { same = m; l = m + 1; } else { r = m - 1; } } if (same == 12) return 0; else if ((b >> (11 - same)) & 1) return +1; return -1; }
풀이 3 (100점)

수를 위에서부터 12, 10, 8, 6진법으로 나타내보자.
6 * 8 * 10 * 12 > 4096 이므로 모든 수를 나타낼 수 있다.

각 자리는 해당 숫자의 번호의 번지수에 비트를 표시하여 나타내면 된다.

이럴 경우, 저장에는 bit_set이 4번, 비교에는 bit_get이 6번 필요하므로, 총 10번의 비교를 통하여 답을 구할 수 있다.

코드 3
#include "cmp.h" static const int base_num[4] = {480, 48, 6, 1}; static const int base_bas[4] = {12, 10, 8, 6}; static const int base_idx[4] = {1, 13, 23, 31}; void remember(int n) { for (int i = 0; i < 4; ++i) { bit_set(base_idx[i] + n / base_num[i]); n %= base_num[i]; } } int compare(int b) { for (int i = 0; i < 4; ++i) { const int bb = b / base_num[i]; b %= base_num[i]; if (bit_get(base_idx[i] + bb)) continue; else if (bb < base_bas[i] / 2) { for (int j = bb - 1; j >= 0; --j) { if (bit_get(base_idx[i] + j)) return +1; } return -1; } else { for (int j = bb + 1; j < base_bas[i]; ++j) { if (bit_get(base_idx[i] + j)) return -1; } return +1; } } return 0; }