[BOJ] 1322_X와 K

X와 K

문제 링크: https://www.acmicpc.net/problem/1322

1322번: X와 K

3차 시도 성공

2차 시도에서 32bit를 64bit로 확장해주니 맞았다.

 

2차시도 내용은 다음과 같다.
b를 비트화 한 내용은 x의 not연산을 수행한 결과와 같다.
그 후 k번째를 읽어 오기 위해서는 b bit 배열에서 1의 자리만 생각했을 때 k의 비트의 true값인 위치의 값들만 읽어 온다.

즉, b bit가 ~~11 1010이고, k(7) bit가 0111일 경우 b bit의 ~~11 1010을 읽어와서

정수화 -> 2^4 + 2^3 + 2^1 = 26을 출력한다.

 

• 정답 코드

  #include<iostream>
  #define bit32 32
  #define bit64 64
  using namespace std;
  unsigned long long int x, k;
  bool bbit[bit64], kbit[bit64];

  int main() {
      cin >> x >> k;

      unsigned long long int xnot = ~x;
      int count1 = 0, count2 = 0;

      // bbit생성
      while (xnot) {
          if (xnot % 2) {
              bbit[count2] = true;
          }
          else;
          count2++;
          xnot /= 2;
      }

      // kbit 생성
      while (k) {
          if (k % 2) {
              kbit[count1] = true;
          }
          else;
          count1++;
          k /= 2;
      }

      unsigned long long int sum = 0;
      for (int i = 0; i < bit64; i++) {
          if (kbit[i]) {
              int saveidx = 0;
              for (int k = 0; k < bit64; k++)
                  if (bbit[k]) {
                      bbit[k] = false;
                      saveidx = k;
                      break;
                  }
              unsigned long long square = 1;
              for (int k = 1; k <= saveidx; k++)
                  square = (unsigned long long)square * 2;
              sum = (unsigned long long) sum + square;
          }
          else {
              for (int k = 0; k < bit64; k++)
                  if (bbit[k]) {
                      bbit[k] = false;
                      break;
                  }
          }
      }
      cout << sum;

      return 0;
  }

2차 시도 실패

• 미해결 코드 
• #include<iostream> #define bit32 32 #define bit64 64 using namespace std; unsigned int x, k; bool bbit[bit32], kbit[bit64]; int main() { cin >> x >> k; unsigned int xnot = ~x; int count1 = 0, count2 = 0; // bbit생성 while (xnot) { if (xnot % 2) { bbit[count2] = true; } else; count2++; xnot /= 2; } // kbit 생성 while (k) { if (k % 2) { kbit[count1] = true; } else; count1++; k /= 2; } unsigned long long int sum = 0; for (int i = 0; i < bit32; i++) { if (kbit[i]) { int saveidx = 0; for (int k = 0; k < bit32; k++) if (bbit[k]) { bbit[k] = false; saveidx = k; break; } unsigned long long square = 1; for (int k = 1; k <= saveidx; k++) square = (unsigned long long)square * 2; sum = (unsigned long long) sum + square; } else { for (int k = 0; k < bit32; k++) if (bbit[k]) { bbit[k] = false; break; } } } cout << sum; return 0; }

1차 시도 실패

X + Y = X | Y 가 성립하기 위한 Y를 만들자.
예제를 OR 연산을 위해 각각 2진수로 만들어보면 0101 + b1b2b3b4 = 0101|b1b2b3b4

b2와 b4가 1일 경우 덧셈의 영향을 미친다. OR연산은 모두 1이어도 1을 유지하기 때문에 1+1 = 0을 방지하기 위해 X가 1일 때 Y는 0이어야 한다. 즉, b2 = b4 = 0이어야 한다.
그렇다면, b1 0 b3 0 중 1번째로 작은 수는 0010 = 2가 된다.

그리고 2번째로 작은 수는 1000, 3번째는 1010, 4번째는 1 0000 5번째는 1 0010식으로 증가하게 된다.

이를 배열로 저장하기에는 20억 칸의 배열이 생성이 불가하므로, 비트연산으로 수행해야 한다.

• 미해결 코드
• #include<iostream> #include<vector> #include<cmath> using namespace std; unsigned int x, k; vector<int> saveIndex, kindex; int main() { cin >> x >> k; unsigned int xnot = ~x; unsigned int y = xnot; int count1 = 0, count2 = 0; while (xnot) { if (xnot % 2) { count1++; saveIndex.push_back(count2); } else; count2++; xnot /= 2; } cout << xnot << endl; count2 = 0; while (k) { if (k % 2) { kindex.push_back(count2); } count2++; k /= 2; } int sum = 0; for (int i = 0; i < kindex.size(); i++) { sum += pow(2, saveIndex[kindex[i]]); } cout << sum; return 0; }

---