3116. Kth Smallest Amount With Single Denomination Combination

• 링크

3116. Kth Smallest Amount With Single Denomination Combination

• 내가 푼 방법

일단, 이 문제는 굉장히 오래 걸려서 푼 개인적으로 어렵다고 느낀 문제이다.
보자말자, lcm(최소공배수)를 활용해서 풀어야 한다는 느낌이 왔지만, 막상 풀려 하니 감이 잡히지 않았다.
그래서, binary search라는 힌트를 얻어냈다.

해당 힌트를 얻어내자마자. 수를 특정하고, 해당 수보다 작거나 같은 수들 중 coins로 만들 수 있는 unique 한 수의 개수를 구하면 되겠다는 것을 알아낼 수 있었다.

하지만, 이게 쉽지 않았다. 처음에는 반복문을 순차적으로 돌면서 현재의 수와 이전의 수들 간의 최소 공배수를 가지고 겹치는 수를 걸러냈는데, 이게 현재의 수와 이전의 수, 단 두 개만 겹치는 것이 아니라 여러 개가 겹칠 수도 있다.

그래서 여기서 더 이상 감을 못 잡겠어, 답을 봤는데, 굉장히 간단했다.

일단, 모든 coins의 조합을 진행해 준다. 그러고서 각자의 최소공배수를 구해주는 것이다.
이렇게 되면, 서로 겹치는 수만을 진행해 주어 나머지 수를 세어줄 필요가 없다. 즉, unique 한 수들의 개수를 한 번에 얻어내는 것이다. 이렇게 하게 되면 이전에 내가 했던 모든 수의 조합을 구한 뒤 여기서 unique 한 모든 수의 개수를 구해주지 않아도 된다. 이 두 개의 난이도 차이가 나는 이유는, 최소 공배수를 곱해줘서 binary search로 정한 값보다 작거나 같은 수의 개수만을 구해주면 되지만, 후자는 정말 다양한 경우를 고려해 줘야 한다.

이렇게 복잡도를 낮출 수 있었다. 하지만, 이해가 안 가는 부분이 1의 개수가 odd 일 때에는 더해주고, even 일 때에는 빼준다. 이게 진짜 이해가 안 갔는데, 다른 solution을 살펴보다가 알게 되었다.

여러 다이어그램의 합집합을 구할 때에는 다음과 같은 다이어그램과 수식이 나오게 된다.

A U B U C = A+B+C - (A∩B) - (A∩C) - (B∩C) +(A ∩ B ∩ C)

만일 3개가 아니라 4개라면 어떻게 될까? 아니면 2개라면?
여기서 규칙을 얻어낼 수 있다.

각각의 다이어그램은 +, 교집합은 -

각각의 다이어그램은 +, 다이어그램 2개의 교집합은 -, 다이어그램 3개의 교집합은 +

위의 그림들과 같이 쭉쭉나아간다.

여기서 볼 수 있는 규칙은, 다이어그램의 교집합을 구할 때, 그 개수가 홀 수일 때에는 +, 짝수일 때에는 - 라는 것이다.

  if(__builtin_popcount(i)&1!=0){
	result+=m/lcmm;
  }else{
	result-=m/lcmm;
  }

__builtin_popcount(i)는 i를 이진수로 나타내었을 때, 1의 개수를 반환해 준다. 즉, 이 말은 선택한 다이어그램의 수를 의미한다. 그렇다면 이해할 수 있을 것이다. 다이어그램의 수가 홀 수일 때에는 if 문에 그렇지 않을 때는 else 문에 걸리기 때문에 더해주거나 빼주게 되는 것이다.

이렇게 해서 이 문제를 해결할 수 있었다.

• 시간 복잡도
  O(log5e10 * 2^coins.size() * coins.size())

• Code

class Solution {
public:
  typedef long long ll;
  typedef vector<int>vi;
  vi c;
  int n;
  long long gcd(long long  a, long long b){
    long long c;
    while (b != 0){
      c = a % b;
      a = b;
      b = c;
    }
    return a;
  }
  long long lcm(long long a, long long b){
    return a*b/gcd(a,b);
  }
  ll getCnt(ll m){
    ll result=0;
    int nn=1<<n;
    for(int i=1;i<nn;i++){
      ll lcmm=1;
      for(int j=0;j<n;j++){
        if((i&(1<<j))!=0){
          lcmm=lcm(lcmm,c[j]);
        }
      }
      if(__builtin_popcount(i)&1!=0){
        result+=m/lcmm;
      }else{
        result-=m/lcmm;
      }
    }
    return result;
  }
  long long findKthSmallest(vector<int>& coins, int k) {
    n=coins.size();
    c=coins;
    sort(c.begin(),c.end());
    ll l=1;
    ll r=5e10;
    ll ans=-1;
    while(l<=r){
      ll m=(l+r)/2;
      ll result=getCnt(m);
      if(result<k){
        l=m+1;
      }else{
        r=m-1;
        ans=m;
      }
    }
    return ans;
  }
};