baekjoon 1256:사전

baekjoon 1256 사전

1256번 사전

접근

이 문제도 dpSkip문제이다. dp(n, m) = “a” n개, “z” m개로 이루어져있는 문자열 개수
dp(n, m) = dp(n-1, m) + dp(n, m-1)
skip(n, m)에서 skip < dp(n-1, m)이면 a로 시작 아니면 z로 시작

코드

//1256
#include <iostream>
#include <array>
#define MAX 1000000000
using namespace std;
array<array<int, 201>, 201> binomial;
int dp(int n, int m);
string skip(int n, int m, int skipCount);
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n, m, k; cin >> n >> m >> k;
  for(int i = 0; i <= 200; i++){
    fill(binomial[i].begin(), binomial[i].end(), -1);
  }
  cout << skip(n, m, k-1) << '\n';


  return 0;
}
string skip(int n, int m, int skipCount){
  if(n == 0){
    string s;
    for(int i = 0; i < m; i++){
      s += "z";
    }
    return s;
  }
  if(m == 0){
    string s;
    for(int i = 0; i < n; i++){
      s += "a";
    }
    return s;
  }
  int pivot = dp(n-1, m);
  int border = dp(n, m);
  if(skipCount >= border) return "-1";
  if(pivot <= skipCount){
    return "z" + skip(n, m-1, skipCount - pivot);
  }
  else{
    //pivot > skipCount
    return "a" + skip(n-1, m, skipCount);
  }
}
int dp(int n, int m){
  //n+m C m이다
  if(n == 0 || m == 0) return 1;
  int sum = n+m;
  int& ret = binomial[sum][m];
  int& ret2 = binomial[sum][n];
  if(ret != -1) return ret2 = ret;
  if(ret2 != -1) return ret = ret2;
  ret = dp(n-1, m) + dp(m-1, n);
  if(ret > MAX) ret = MAX;
  ret2 = ret;
  return ret;
}

배운 점

dpSkip 문제였다.