BOJ 11469 - Distribution in Metagonia

BOJ 11469 - Distribution in Metagonia

어떤 자연수 $n$을 $2^x \cdot 3^y$ 의 합으로 나타내야 하는데, 각 항들은 서로를 나눌 수 없어야 한다.

$2^{x_1}3^{y_1}$와 $2^{x_2}3^{y_2}$ 가 있을 때 서로를 나누는 조건은 일반성을 잃지 않고 $x_1 \le x_2$ 라 할 때, $x_1 \le x_2$그리고 $y1 \le y2$ 가 동시에 만족될 때이다.

그러므로 각 항들에서 2와 3의 지수는 2의 지수가 커지면 3의 지수가 작아지는 식으로 항들이 구성됨을 캐치할 수 있다.

해결은 다음과 같이 했다.

---

$N$이 홀수라고 하자. 그럼 이 때는 항상 $3$만 있는 어떠한 항이 필요하다.

따라서 $3^0, 3^1, \cdots$ 로 진행하며 완전탐색을 해준다.

그리고 $N-3^y$ 만큼 해준 값으로 다음 재귀함수를 호출한다.

이제 $N$이 짝수라고 하자. $N$이 짝수임은 정답에 존재하는 모든 항들에 $2$의 거듭제곱수를 1 증가시켜주는 것과 동일하고, 이는 $x_1 \le x_2$ 조건에 아무런 영향을 끼치지 않는다.

왜냐면 모든 항에 동등하게 1씩 더해지기 때문에 $3$의 거듭제곱 수들의 대소관계만 유지해주면 올바르게 해답을 찾아나갈 수 있다.

조금 더 빠르게 돌리기 위해 $3^y$를 포함한 상태라면, 다음 $3$의 거듭제곱 수는 $y-1$ 부터 탐색해나가는 것이다.

2의 거듭제곱수는 짝수를 만날때마다 1씩 증가시켜주므로, 이전에 찾아낸 값이 $2$의 거듭제곱수가 더 작은 상태이므로 증가하고 있는 흐름이고,

3의 거듭제곱수는 감소하고 있는 흐름으로 탐색해주어야 옳다.

const int MAX = 1e18;  
vi pw2, pw3;  
int P2, P3;  
void pre_calc() {  
   pw2.pb(1), pw3.pb(1);  
   while (pw2.back() < MAX) pw2.pb(pw2.back() * 2);  
   while (pw3.back() < MAX) pw3.pb(pw3.back() * 3);  
   pw2.pop_back();  
   pw3.pop_back();  
  
   P2 = sz(pw2);  
   P3 = sz(pw3);  
}  
  
bool f = 0;  
vector<pi> ans;  
int N;  
void fn(int n, int two) {  
   if (n == 0) {  
      cout << sz(ans) << endl;  
      for (auto[a, b]: ans) {  
         cout << pw2[a] * pw3[b] << ' ';  
      }  
      cout << endl;  
      f = 1;  
      return;  
   }  
   if (n % 2) {  
      for (int i = sz(ans) ? ans.back().se - 1 : P3 - 1; i >= 0 && !f; i--) {  
         if (pw3[i] > n) continue;  
         ans.pb({two, i});  
         fn(n - pw3[i], two);  
         ans.pop_back();  
      }  
   } else {  
      fn(n / 2, two + 1);  
      if (f) return;  
   }  
}  
  
void solve() {  
   f = 0;  
   int n;  
   cin >> n;  
   fn(n, 0);  
}