“

[문제 733] 핵심 개념 및 풀이 전략

원소의 곱이 6의 배수가 되는 부분집합의 개수를 찾는 문제입니다. 731번과 유사합니다.

접근법:
곱이 6의 배수가 되려면, **2의 배수와 3의 배수를 적어도 하나씩** 포함해야 합니다.
1. A={3,4,5,6,7}. 2의 배수 관련 원소는 {4,6}, 3의 배수 관련 원소는 {3,6} 입니다.
2. (경우 1: 6을 포함) 6이 포함되면 곱은 항상 6의 배수입니다. 6을 반드시 포함하는 부분집합의 개수는 2^(5-1)=16개. 이 중 n(X)≥2를 만족하지 않는 {6}을 제외하면 15개.
3. (경우 2: 6을 미포함, 3과 4를 포함) 3과 4를 반드시 포함하고 6은 포함하지 않는 부분집합의 개수는 2^(5-1-1-1)=4개. 이들은 모두 n(X)≥2를 만족.
4. 두 경우의 수를 더합니다.

주의할 점:
6은 2의 배수이자 3의 배수이므로, 6의 포함 여부를 기준으로 경우를 나누는 것이 효율적입니다.

”

곱이 6의 배수가 되는 부분집합의 개수 찾기