[BOJ] 26084 - DPS

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

BOJ - DPS

문제 유형: 수학, 조합론, 문자열 처리

문제 난이도: Silver II

시간 제한: 1초

메모리 제한: 1024MB

 

문제

ICPC는 세 명이 한 팀을 이뤄 참가하는 국제 대학생 프로그래밍 대회이다. ICPC에 참가하는 각 팀의 이름은 세 팀원의 핸들 첫 글자를 임의의 순서로 이어 붙인 것이다. 핸들이란 Baekjoon Online Judge와 같은 온라인 채점 사이트에서 사용하는 고유한 ID이다.

예를 들어 핸들이 각각 DONGGAS, PICASSO, SEMTEO인 세 명으로 이루어진 팀의 이름은 DPS, DSP, PDS, PSD, SDP, SPD 중 하나이다. 또, 핸들이 각각 RAARARAARA, WBCHO, WEASEL인 세 명으로 이루어진 팀의 이름은 RWW, WRW, WWR 중 하나이다.

팀 이름 S와 N명의 핸들이 주어지면, N명으로 팀 S를 구성하는 모든 경우의 수를 구해보자.

 

입력

첫째 줄에 팀 이름 S가 주어진다. 팀 이름 S는 영어 대문자 3개로 이루어져 있다.

둘째 줄에 사람의 수를 나타내는 양의 정수 N(3≤N≤50000)이 주어진다.

셋째 줄부터 N명의 핸들이 한 줄에 하나씩 주어진다. 각 핸들의 길이는 1이상 10이하이다.

모든 사람의 핸들은 영어 대문자로만 이루어진 공백이 없는 문자열이다. 또, 모든 사람의 핸들은 서로 다르다.

 

출력

첫째 줄에 팀 S의 구성으로 가능한 모든 경우의 수를 출력한다.

출력이 32비트 정수형 타입의 표현 범위를 초과할 수 있으므로 언어에 따라 아래와 같은 적절한 64비트 정수형 타입을 이용하여 출력해야 한다.

• C/C++: long long
• JAVA: long
• Kotlin: Long

 

풀이

각 이름들의 첫 접두어만 추출해서, 문자 개수를 저장해놓는다.

S를 읽으면서 빈도를 구한다.

각 빈도에 따라서 조합의 수 nCr을 곱누적한다.

 

코드

C++

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  string s;
  cin >> s;

  int n;
  cin >> n;

  vector<ll> charcnt(26, 0);
  string temp;
  for (int i = 0; i < n; ++i) {
    cin >> temp;
    charcnt[temp[0] - 'A']++;
  }

  vector<int> freq(26, 0);
  for (int i = 0; i < 3; ++i) {
    freq[s[i] - 'A']++;
  }

  ll ans = 1;
  for (int i = 0; i < 26; ++i) {
    if (freq[i] > 0) {
      ll x = 1;
      for (int j = 0; j < freq[i]; ++j) {
        x *= (charcnt[i] - j);
      }
      for (int j = 0; j < freq[i]; ++j) {
        x /= j + 1;
      }
      ans *= x;
    }
  }

  cout << ans << "\n";

  return 0;
}