“
[문제 766] 핵심 개념 및 풀이 전략
각 부분집합의 최소 원소들을 모두 더하는 문제입니다.
접근법:
1. 각 원소가 ‘최소 원소’로서 몇 번이나 선택되는지를 셉니다.
2. (1이 최소 원소인 경우) 1을 반드시 포함하고, 1보다 작은 원소는 없는 부분집합의 개수입니다. 이는 1을 제외한 나머지 원소 {2, 4, …, 64} (6개)로 만들 수 있는 부분집합의 개수인 2⁶과 같습니다.
3. (2가 최소 원소인 경우) 2를 반드시 포함하고, 1은 포함하지 않는 부분집합의 개수입니다. 이는 2와 1을 제외한 나머지 5개 원소로 만들 수 있는 부분집합의 개수인 2⁵와 같습니다.
4. 이와 같은 방식으로 각 원소에 대해 계산합니다.
5. 최종 합 = (1 × 2⁶) + (2 × 2⁵) + (4 × 2⁴) + … + (64 × 2⁰)
주의할 점:
최소 원소 문제는 ‘그 원소보다 작은 원소는 모두 제외’하는 조건이 숨어있다는 것을 파악하는 것이 핵심입니다.
”
각 부분집합의 최소 원소들의 총합 구하기