[백준][C++]1256번 사전

문제

https://www.acmicpc.net/problem/1256

1256번: 사전

 

 

풀이

• a와 z로 만들 수 있는 모든 경우의 수

= N + M개에서 N개를 뽑는 경우의 수 = N + M개에서 M개를 뽑는 경우의 수

 

• 조합 점화식

D[i][j] = D[i - 1][j] + D[i - 1][j - 1]

 

• 문자 선택 기준
  • (T : 현재 자릿수에서 a를 선택했을 때 남은 문자로 만들 수 있는 모든 경우의 수)
  • T ≥ K : 현재 자리 문자를 a로 선택
  • T < K : 현재 자리 문자를 z로 선택, K = K - T로 업데이트

 

조합(Combination) 알고리즘

조합(Combination) 알고리즘

 

 

코드

#include <iostream>
#include <vector>
using namespace std;

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

  int N, M, K;
  cin >> N >> M >> K;

  // 조합 테이블 초기화
  int DP[202][202] = {0};
  for(int i = 1; i <= N + M; i++)
  {
    DP[i][0] = 1;
    DP[i][1] = i;
    DP[i][i] = 1;
    for(int j = 2; j < i; j++)	// 고르는 수의 개수가 전체 개수를 넘을 수 없음
    {
      DP[i][j] = min(DP[i - 1][j - 1] + DP[i - 1][j], 1000000001);	// K 범위가 넘어가면 범위 최댓값 지정
    }
  }

  if(DP[N + M][N] < K)	// 주어진 자릿수로 만들 수 없는 K번째 수이면
  {
    cout << "-1";	// -1 출력하기
    return 0;
  }

  while(1)
  {
    if(DP[N + M - 1][N - 1] >= K)	// a를 선택했을 때 남은 문자로 만들 수 있는 모든 경우의 수가 K보다 크면
    {
      cout << "a";	// a 출력하기
      N--;	// a 문자 개수 감소
      if(N == 0)
      {
        while(M)
        {
          cout << "z";
          M--;
        }
        break;
      }
    }
    else	// 모든 경우의 수가 K보다 작으면
    {
      cout << "z";	// z 출력하기
      K -= DP[N + M - 1][N - 1];	// K값 업데이트
      M--;	// z 문자 개수 감소
      if(M == 0)
      {
        while(N)
        {
          cout << "a";
          N--;
        }
        break;
      }  
    }
  }  

  return 0;
}

 

 

오답

조합 테이블 초기화 시, K 범위가 넘어가면 범위 최댓값 저장

 

#include <iostream>
using namespace std;

static int N, M, K;
static long D[202][202];

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

  cin >> N >> M >> K;

  // 조합 테이블 초기화
  for(int i = 0; i <= 200; i++)
  {
    for(int j = 0; j <= i; j++)
    {
      if(j == 0 || j == i)
      {
        D[i][j] = 1;
      }
      else
      {
        D[i][j] = D[i - 1][j - 1] + D[i - 1][j];
        // K 범위가 넘어가면 범위 최댓값 저장
        if(D[i][j] > 1000000000)
        {
          D[i][j] = 1000000001;
        }
      }
    }
  }
  if(D[N + M][M] < K)  // 주어진 자릿수로 만들 수 없는 K번째 수이면
  {
    cout << "-1";
  }
  else
  {
    while(!(N == 0 && M == 0))  
    {
      if(D[N - 1 + M][M] >= K)	// a를 선택했을 때 남은 문자로 만들 수 있는 모든 경우의 수가 K보다 크면
      {
        cout << "a";
        N--;
      }
      else	// 모든 경우의 수가 K보다 작으면
      {
        cout << "z";
        K = K - D[N - 1 + M][M];  // K값 업데이트
        M--;
      }
    }
  }

}

 

[ 정답코드 예시 ]

규완이의 사전에 수록돼 있는 문자열의 개수

= a와 z로 만들 수 있는 모든 경우의 수

= DP[N + M][N] = DP[N + M][M]