[백준 28239] 배고파(Easy) (C#, C++) - soo:bak

문제 링크

28239번 - 배고파(Easy)

설명

양의 정수 m이 주어질 때, 2^x + 2^y = m을 만족하는 x와 y를 구하는 문제입니다.

x ≤ y이며, 조건을 만족하는 쌍이 항상 존재합니다.

접근법

m의 이진 표현에서 1인 비트의 위치를 확인합니다.

1인 비트가 두 개이면 그 위치가 x와 y입니다.

1인 비트가 한 개이면 m이 2의 거듭제곱이므로, x = y = p - 1이 됩니다.

---

Code

C#

using System;
using System.Collections.Generic;

class Program {
  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    for (var t = 0; t < n; t++) {
      var m = long.Parse(Console.ReadLine()!);
      var bits = new List<int>();
      for (var i = 0; i <= 60; i++) {
        if (((m >> i) & 1L) == 1) bits.Add(i);
      }

      if (bits.Count == 1) {
        var p = bits[0];
        Console.WriteLine($"{p - 1} {p - 1}");
      } else Console.WriteLine($"{bits[0]} {bits[1]}");
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;

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

  int n; cin >> n;
  for (int t = 0; t < n; t++) {
    ll m; cin >> m;
    vi pos;
    for (int i = 0; i <= 60; i++) {
      if (m & (1LL << i)) pos.push_back(i);
    }
    if (pos.size() == 1) {
      int p = pos[0];
      cout << p - 1 << " " << p - 1 << "\n";
    } else cout << pos[0] << " " << pos[1] << "\n";
  }

  return 0;
}