nchoosek, string, unique를 이용한 경우의 수 문제 풀이

 

 

어디서 줏었는지 기억이 나지 않는다. 아마 고등~대학 물리학, 수학 단톡방이 아니었을까 싶다.

 

50원짜리 5개를 모아서 250원을 만드는 것인데, A, B, C, D가 갖고 있는 동전 개수가 다르다. 동전을 내지 않는 사람이 있어도 된다. 따라서

• A가 5개 내도 되고

• A가 3개, B가 2개 내도 되고

• A가 1개, B가 1개, C가 1개, D가 2개 내도 된다.

 

결국 이 문제는 아래를 묻는 것이다.

 

"AAAAAABBBBCCCDD"에서 문자 5개를 고르는 경우의 수

 

${}_{15}C_5$는 아니다. 중복된 문자들이 있기 때문이다.

 

생각하기 귀찮았던 나는(...) 이딴 코드를 짜고 있었다.

 

coins = 'ABCD';

t = table2array(combinations(coins, coins, coins, coins, coins));

t((sum(t == 'B', 2) > 4), :) = [];
t((sum(t == 'C', 2) > 3), :) = [];
t((sum(t == 'D', 2) > 2), :) = [];

t = mat2cell(t, ones(size(t, 1), 1), 5);
t = cellfun(@sort, t, 'UniformOutput', false);

disp(unique(t))
length(unique(t))

 

• combinations로 $4^5 = 1024$개의 모든 순열을 만든다.

• B가 4개보다 더 낼 수는 없으므로 B가 4개보다 많은 경우를 제외한다.

• C가 3개보다 더 낼 수는 없으므로 (상동).

• D가 2개보다 더 낼 수는 없으므로 (상동).

• 중복 제거를 위해 각 문자열을 sort 한다. (그걸 위해 각 row를 하나의 cell로 만든다.)

• unique를 입힌다.

 

답이 나오긴 나온다.

 

문제는, 사실 한줄컷이 가능하다는 것.

 

 

 

unique(string(nchoosek('AAAAAABBBBCCCDD', 5)))

 

• nchoosek(v, n)에서 v가 벡터이고 n이 자연수이면 v의 원소 중 n개를 고르는 모든 조합을 만들어준다.

• 이때 v의 원소 중 중복된 것이 있어도 모두 다른 것으로 간주한다.

• 그리고 조합(combination)이므로 이미 sort가 되어 있다.

• 아래는 간단한 경우의 예제이다.

 

>> nchoosek('AABC', 2)
ans =
  6×2 char array
    'AA'
    'AB'
    'AC'
    'AB'
    'AC'
    'BC'
>>

 

 

• unique를 입혀서 중복된 것을 없애야 하는데, string은 char array의 각 row를 하나의 string으로 만든다.

 

>> string(nchoosek('AABC', 2))
ans = 
  6×1 string array
    "AA"
    "AB"
    "AC"
    "AB"
    "AC"
    "BC"
>>

 

• 이제 unique를 입히면 끝난다.

 

>> unique(string(nchoosek('AABC', 2)))
ans = 
  4×1 string array
    "AA"
    "AB"
    "AC"
    "BC"
>>

 

• 아래는 원래 문제에 적용한 결과이다.

 

>> unique(string(nchoosek('AAAAABBBBCCCDD', 5)))
ans = 
  41×1 string array
    "AAAAA"
    "AAAAB"
    "AAAAC"
    "AAAAD"
    "AAABB"
    "AAABC"
    "AAABD"
    "AAACC"
    "AAACD"
    "AAADD"
    "AABBB"
    "AABBC"
    "AABBD"
    "AABCC"
    "AABCD"
    "AABDD"
    "AACCC"
    "AACCD"
    "AACDD"
    "ABBBB"
    "ABBBC"
    "ABBBD"
    "ABBCC"
    "ABBCD"
    "ABBDD"
    "ABCCC"
    "ABCCD"
    "ABCDD"
    "ACCCD"
    "ACCDD"
    "BBBBC"
    "BBBBD"
    "BBBCC"
    "BBBCD"
    "BBBDD"
    "BBCCC"
    "BBCCD"
    "BBCDD"
    "BCCCD"
    "BCCDD"
    "CCCDD"
>>

 

 

이 글 작성에 아이디어를 주신 티비보는 무지님께 감사 말씀 드립니다.

 

끗