[SWEA] 9480. 민정이와 광직이의 알파벳 공부

[SWEA] 9480. 민정이와 광직이의 알파벳 공부(D3)

오늘은 이걸 풀것입니다.

 

..라고 쓴 지 5일 만에 문제를 풀었는데요.

 

D3라서 가볍게 생각하고 풀려고 했고 문제 읽을 때도 별로 복잡하게 생각하지 않았는데.. 생각보다 복잡하네요? 제가 정해를 몰라서 그럴 수도 있고.
아무튼 생각보다 오래 걸렸고 복잡하게 풀었습니다. (긴 변명)

 

N개의 주어진 단어들의 조합이 전체 알파벳을 포함하도록 구성하는 문제입니다.
각 단어의 길이는 1부터 100까지 존재할 수 있고, 단어는 최대 15개까지 주어질 수 있습니다.

아래는 코드 및 풀이.

 

비트 연산과 조합을 사용해서 풀었습니다.
각 단어가 포함하고 있는 알파벳을 비트 연산 <<(shift) 와 |(OR) 을 사용해 정수형 변수에 저장했고,
단어가 1개인 경우부터 N개인 경우까지 순회하면서 해당 조합이 전체 알파벳을 포함하는지 확인했습니다.
조합은 next_permutation()을 활용했습니다.

 

개인적으로 까다로웠던 부분은 조합 부분인데, 이 풀이에 대해선 아직도 별로 확신이 없네요.
일단, 주어진 단어의 수 N에 대해, 가능한 전체 조합의 수를 구합니다. (getTotalCases())

N = 5 일 때:

전체 조합의 수(N=5) = 5C1 + 5C2 + 5C3 + 5C4 + 5C5
                 = 5 + 10 + 10 + 5 + 1 
                 = 31

N = 4 일 때:

전체 조합의 수(N=4) = 4C1 + 4C2 + 4C3 + 4C4
                 = 4 + 6 + 4 + 1 
                 = 15

이 문제에서 단어를 0개 뽑는 경우의 수는 고려 대상이 아니므로 제외했습니다.
조합의 합에 대한 규칙이 기억 안 나서 이런 헛짓을 했는데,
전체 조합의 합은 애초에 2^N 이고 이 가짓수에서 아무것도 뽑지 않는 경우 하나만 빼면 전체 단어 조합의 수를 구할 수 있습니다.

전체 조합의 수 = 2^N - 1

전체 조합의 수 tcs를 구한 다음(line 32), 단어가 1개인 경우부터 N개인 경우까지 순회합니다.
이때, i번째 순회에서 i개의 단어를 뽑는 조합을 구현하기 위해 정수형 배열 comb를 만듭니다. (makeCombSet())
next_permutation()을 활용하기 위해, comb 배열은 0으로 채워져 있어야 하며, 뒤(N-1번째)에서부터 i개의 원소는 1로 채워지도록 합니다.

 

불필요한 순회를 줄이기 위해, i개를 뽑는 단어 조합이 모두 알파벳 전체를 포함할 경우 순회를 멈춥니다.
bool형 변수 keep을 사용해, 한 번이라도 알파벳을 모두 포함하지 않는 조합이 있을 경우 계속 순회하고(line 53),
그렇지 않을 경우 반복문을 탈출합니다.(line 56)

 

사실 백트래킹을 활용해서 가능성을 줄여 나가는 쪽이 더 빠를 것 같은데 구현을 못 하겠어서! 그 풀이는 못했구요
다음에 백트래킹에 익숙해지면 다시 풀어보고 싶네요.

 

근데 진짜 제가 정해를 못 찾은 건가요 아니면 D3가 복잡해진 건가요?
이게 D4까진 아니라고 생각하지만..