baekjoon 2248:이진수 찾기

baekjoon 2248 이진수 찾기

2248번 이진수 찾기

접근

dp의 2번째 유형이다. k번째 수를 찾으라고 하는 dp이다. 직접 1번째부터 k번째 까지 다 찾게 되면
너무 오래걸리기 때문에 skip을 이용해서 뛰어 넘어서 구한다. 그 뛰어 넘을려면 경우에 맞는 수를 직접
다 나열하는 것이 아닌 dp를 이용해서 바로 개수만 return 하도록 해야한다. 그런 뒤 skip해야하는 수와
비교하여 k번째 수를 결정해 나간다.
여기선 dp(n, l) = n자리 이진수중 1이 l개 이하인 것이다.
dp(n, l) = dp(n-1, l-1) + dp(n-1, l) 이 점화식이다.
skip은 k번째라면 k-1번 skip하는 것으로 해야한다.
dp(n, l)인 상태에서 p번 skip 상태라면 dp(n-1, l)과 비교하여 dp(n-1, l) > p 이면
n자리 수가 0인 경우의 수 안에 p번 skip상태가 있는 것이므로 n자리수에 0을 넣는다.
dp(n-1, l) <= p이면 초과한다는 의미로 n자리수에 1을 넣는다.

코드

//2248
#include <iostream>
#include <array>
#include <vector>
using namespace std;
array<array<int, 32>, 32> cache;
int dp(int n, int l);
string skip(int n, int l, long long int p);
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);

  int n, l; long long int p;
  cin >> n >> l >> p;
  for(int i = 0; i <= n; i++){
    fill(cache[i].begin(), cache[i].end(), -1);
  }
  cout << skip(n, l, p-1) << '\n';
  //p-1개 건너 뛰고 출력하겠다
  //즉, 0되면 출력임



  return 0;
}
string skip(int n, int l, long long int p){
  // cout << n << ' ' << l << ' ' << p << '\n';
  if(n == 0) {
    // cout << "n=0\n";
    // if(p == 0) cout << "p=0\n";
    return "";
  }
  if(l == 0){
    // cout << "l=0\n";
    // if(p == 0) cout << "p=0\n";
    string s;
    for(int i = 0; i < n; i++){
      s += '0';
    }
    return s;
  }

  if(dp(n-1, l) > p){
    return "0" + skip(n-1, l, p);
  }
  else{

    return "1" + skip(n-1, l-1, p-dp(n-1, l));
  }
}
int dp(int n, int l){
  if(n < l) return dp(n, n);
  if(n == l) return 1 << n;
  if(n == 0 || l == 0) return 1;
  int& ret = cache[n][l];
  if(ret != -1) return ret;
  ret = dp(n-1, l);
  if(l > 0) ret += dp(n-1, l-1);
  return ret;

}

배운 점

dpSkip 문제였다.