백준 #30463 K-문자열

문제 링크

[30463 K-문자열]

문제 설명

길이가 10인 0~9사이의 숫자로 이루어진 문자열이 여러개 주어지고 각 문자열을 쌍을 지어 이어 붙였을 때 서로다른 문자의 개수가 K인 문자열의 개수를 구하는 문제

코드

import sys
input = sys.stdin.readline


N, K = map(int, input().split())
count = [0] * 1024
for _ in range(N):
    arr = list(map(int, input().rstrip()))
    bit = 0
    for x in arr:
        bit |= (1 << x)

    count[bit] += 1

ans = 0

for i in range(1 << 10):
    for j in range(i, 1 << 10):
        if not count[i] or not count[j]:
            continue
        num = i | j
        if bin(num)[2:].count("1") == K:
            if i == j:
                ans += (count[i] * (count[i] - 1) // 2)
            else:
                ans += (count[i] * count[j])

print(ans)

풀이

비트마스킹으로 풀이했다. 0부터 9사이의 숫자 유무를 저장하기 위해 크기가 1024인 배열을 만들었고 각 문자열을 저장했다. 이중 for 문을 돌면서 2진수로 변환했을 때 1의 개수가 K인 문자열에 대해서 OR 연산 전의 숫자가 같다면 $ \binom{n}{2} $ 를 해주었다. 이유는 순서쌍 (i, j) 에 대하여 i < j인 경우만 세어주어야 하기 때문이다. OR 연산 전의 숫자가 다르다면 각각의 개수를 곱해주어서 정답에 더해주었다.