TOUGH
최다빈출 왕중요
부분집합의 개수
최대 원소 기준 분류
출제의도
앞 문항이 ‘최소 원소’로 묶는 연습이었다면, 이 문항은 방향을 뒤집어 최대 원소로 묶습니다. 여기에 ‘원소의 개수가 2 이상’이라는 조건이 하나 더 붙는데, 이 한 줄이 문제의 난이도를 결정합니다. 조건이 없다면 단순한 분류 문제지만, 조건이 붙는 순간 각 경우마다 원소가 하나뿐인 부분집합을 빼주는 보정이 필요해집니다.
TOUGH 스텝에 배치된 이유가 바로 이 보정입니다. 대부분의 오답은 계산 실수가 아니라 −1을 빠뜨린 데서 나옵니다. 게다가 최대 원소가 1인 경우는 아예 존재할 수 없다는 점까지 스스로 판단해야 하므로, 조건을 개수 세기에 반영하는 훈련으로는 최적의 문항입니다.
단계별 힌트
힌트 1단계 · 발상과 연결고리
구하는 값이 각 부분집합의 최대 원소들의 합이므로, 최대 원소를 기준으로 분류합니다. 그런데 그 전에 확인할 것이 있습니다. 최대 원소가 1인 부분집합이 존재할 수 있을까요?
최대가 1이면 3, 5, 7, 9는 모두 들어갈 수 없으므로 그 부분집합은 {1}뿐인데, 원소가 하나뿐이라 조건에 어긋납니다. 따라서 최대 원소가 될 수 있는 값은 3, 5, 7, 9의 네 가지입니다. 경우의 수를 세기 전에 이 네 가지로 범위를 좁히고 시작하세요.
힌트 2단계 · 풀이 설계 (계산은 직접 해보세요)
최대 원소를 x로 고정하면 ① x는 반드시 포함, ② x보다 큰 원소는 모두 제외, ③ x보다 작은 원소는 자유입니다. x보다 작은 원소가 m개라면 이런 부분집합은 2m개입니다.
여기서 한 단계가 더 남습니다. 그 2m개 중에는 {x} 하나짜리가 정확히 한 개 섞여 있고, 이것만은 ‘원소 2 이상’ 조건을 만족하지 못합니다. 그래서 각 경우의 개수는 2m−1입니다. 단, 최대가 3인 경우는 작은 원소가 1 하나뿐이므로 직접 확인하는 편이 빠릅니다.
정답 확인
정답 ③ M₁+M₂+M₃+⋯+Mₙ = 202
상세 해설
두 번째 이미지에는 집합이 {2, 4, 6, 8, 10}으로 바뀐 내신연계 출제문항 405번의 해설이 함께 실려 있습니다. 개수를 세는 구조는 완전히 같고 곱해지는 값만 달라지므로, 본 문항 직후에 이어서 풀면 유형이 확실히 굳어집니다.
풀이 흐름 한눈에 정리
해설 이미지의 계산을 따라가기 전에 전체 흐름을 문장으로 정리하면 다음과 같습니다.
STEP A최대인 원소에 따라 부분집합의 개수 세기
원소의 개수가 2 이상이어야 하므로 최대 원소 Mₖ가 가질 수 있는 값은 3, 5, 7, 9입니다.
- 최대가 3인 경우 : 5, 7, 9 제외, 1은 반드시 포함해야 개수가 2가 되므로 {1, 3} 하나뿐 → 1개
- 최대가 5인 경우 : 7, 9 제외, {1, 3}은 자유 → 25−1−2−1 = 4−1 = 3개 ({5} 제외)
- 최대가 7인 경우 : 9 제외, {1, 3, 5}는 자유 → 25−1−1−1 = 8−1 = 7개 ({7} 제외)
- 최대가 9인 경우 : {1, 3, 5, 7}이 자유 → 25−1−1 = 16−1 = 15개 ({9} 제외)
1+3+7+15 = 26개인데, 전체 부분집합 32개에서 공집합 1개와 원소 1개짜리 5개를 뺀 26과 일치하므로 분류가 정확합니다.
STEP B최대 원소들의 합 구하기
각 경우의 (값)×(개수)를 더하면
M₁+M₂+⋯+Mₙ = 3×1 + 5×3 + 7×7 + 9×15 = 3+15+49+135 = 202
1등급 다른 풀이 · 조건을 나중에 빼는 보정법
−1을 매번 챙기는 것이 부담스럽다면, 조건을 잠시 잊고 계산한 뒤 마지막에 한꺼번에 빼는 방법이 훨씬 안전합니다.
먼저 개수 조건 없이 공집합만 제외한 31개 부분집합에 대해 최대 원소의 합을 구합니다. 최대가 1인 것은 1개, 3인 것은 2개, 5인 것은 4개, 7인 것은 8개, 9인 것은 16개이므로
1×1 + 3×2 + 5×4 + 7×8 + 9×16 = 1+6+20+56+144 = 227
이제 여기서 빠져야 할 것은 원소가 1개인 부분집합 {1}, {3}, {5}, {7}, {9}뿐이고, 이들의 최대 원소는 자기 자신이므로 합은 1+3+5+7+9 = 25입니다. 따라서 구하는 값은 227−25 = 202입니다.
이 방식의 장점은 −1을 네 번 신경 쓰는 대신 마지막에 딱 한 번만 보정한다는 점입니다. ‘원소 3개 이상’, ‘원소 4개 이하’처럼 조건이 달라져도 빼야 할 대상만 바꾸면 그대로 통하므로, 변형 문항에 훨씬 강합니다.
실수를 줄이는 전략
- −1 보정을 빠뜨리면 3+20+56+144 = 223이 나옵니다. 선택지에 없는 값이니 계산 직후 답이 보기와 어긋나면 이 보정부터 의심하세요.
- 최대 원소를 정했으면 그보다 큰 원소는 전부 제외, 작은 원소는 자유입니다. 앞 문항(최소 기준)과 방향이 정반대라는 점을 의식하고 푸세요.
- 최대가 3인 경우를 공식 22−1 = 3으로 잘못 세지 않도록 주의하세요. 자유로운 원소가 1 하나뿐이므로 21−1 = 1이 맞습니다.
- 개수의 총합이 26이 되는지 점검하세요. 전체 32개에서 공집합 1개와 한원소집합 5개를 뺀 값과 맞아야 합니다.
- 묻는 것은 부분집합의 개수 n이 아니라 최대 원소들의 합입니다. 마지막에 값을 곱했는지 확인하고 답을 적으세요.
엄선된 풀이 영상
위 풀이 흐름을 영상으로 한 번 더 확인하고 싶다면 재생 버튼을 누르세요.