🧙♂️ 백준 2309번 일곱 난쟁이 3가지 문제 풀이
https://www.acmicpc.net/problem/2309
백준 2309번 문제는 아홉 명의 난쟁이 중 진짜 일곱 난쟁이를 찾는 문제입니다. 일곱 난쟁이의 키 합이 100이 된다는 조건을 활용하여, 아홉 개의 숫자 중 일곱 개를 선택하는 여러 가지 방법을 소개합니다.
1. 📝 문제 이해하기
1.1. 문제 조건
– 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다.
– 주어지는 키는 100을 넘지 않는 자연수이다.
– 아홉 난쟁이의 키는 모두 다르다.
– 일곱 난쟁이의 키의 합은 100이다.
– 가능한 정답이 여러 가지인 경우 아무거나 출력한다.
1.2. 출력 요구사항
– 일곱 난쟁이의 키를 오름차순으로 출력해야 한다.
– 일곱 난쟁이를 찾을 수 없는 경우는 없다(답은 항상 존재).
2. 🧮 접근 방법 1: 조합(Combination) 활용
2.1. 조합 라이브러리 활용
– itertools 모듈의 combinations 함수를 사용하였다.
– 아홉 개 중 일곱 개를 선택하는 모든 조합을 확인하였다.
– 각 조합의 합이 100이 되는 경우를 찾았다.
from itertools import combinations
import sys
input = sys.stdin.readline
height = [int(input()) for _ in range(9)]
for comb in combinations(height, 7):
if sum(comb) == 100:
for height in sorted(comb):
print(height)
break # 여러 개의 정답이 나올 수 있으므로, 첫 번째로 찾은 것을 출력하고 종료2.2. 주의점: 여러 답 처리
– break를 사용하지 않으면 답이 여러 개일 경우 모두 출력되는 오류가 발생한다.
– 문제 요구사항은 가능한 답 중 하나만 출력하는 것이다.
3. 🔄 접근 방법 2: 무식한 방법(7중 for문)
3.1. 7중 for문 구현
– 조합 라이브러리 없이 7중 for문으로 직접 구현할 수 있다.
– 모든 가능한 7개 선택을 확인하는 방법이다.
import sys
input = sys.stdin.readline
height = [int(input()) for _ in range(9)]
for i in range(9):
for j in range(i+1, 9):
for k in range(j+1, 9):
for m in range(k+1, 9):
for n in range(m+1, 9):
for o in range(n+1, 9):
for p in range(o+1, 9):
if height[i] + height[j] + height[k] + height[m] + height[n] + height[o] + height[p] == 100:
result = [height[i], height[j], height[k], height[m], height[n], height[o], height[p]]
result.sort()
for r in result:
print(r)
sys.exit(0)4. 💡 접근 방법 3: 역발상을 통한 풀이
4.1. 2개 선택 아이디어
– 아홉 개 중 일곱 개를 선택하는 것은 아홉 개 중 두 개를 제외하는 것과 같다.
– 전체 합에서 두 난쟁이의 키를 빼서 100이 되는 경우를 찾았다.
– 이중 for문만으로 해결 가능하다.
import sys
input = sys.stdin.readline
height = [int(input()) for _ in range(9)]
height.sort()
total = sum(height)
for i in range(8):
for j in range(i+1, 9):
if total - height[i] - height[j] == 100:
for k in range(9):
if i != k and j != k:
print(height[k])
sys.exit(0)5. 🔍 반복문 탈출 및 함수화 방법
5.1. 반복문 탈출 전략
– break를 사용하여 현재 반복문만 탈출할 수 있다.
– **sys.exit(0)**를 사용하면 프로그램 전체를 종료할 수 있다.
– 플래그 변수를 사용하여 상위 반복문도 탈출할 수 있다.
5.2. 함수화 방법
– 함수로 분리하여 return으로 모든 반복문 탈출이 가능하다.
– 코드 가독성이 향상되고 유지보수가 용이해진다.
6. 📊 완전 탐색의 의미와 시간 복잡도
6.1. 완전 탐색 접근법
– 문제 해결 방법이 떠오르지 않을 때 완전 탐색으로 먼저 접근해볼 수 있다.
– 모든 경우를 다 살펴보는 가장 무식한 방법이다.
– 시간 복잡도가 허용되는 경우 유효한 전략이다.
6.2. 시간 복잡도 분석
– 이 문제에서 9C7(=9C2)는 36가지 경우밖에 없다.
– N이 작아 시간 복잡도를 따지는 것이 큰 의미가 없는 문제였다.
– 항상 최악의 경우를 고려하여 시간 복잡도를 계산해야 한다.
7. 🎯 결론
– 문제를 접했을 때 가장 먼저 완전 탐색 방법으로 접근해보는 것이 좋다.
– 시간 제한 내에 해결 가능하면 완전 탐색으로 구현한다.
– 시간 초과가 발생할 것 같으면 더 효율적인 알고리즘(그리디, DP 등)을 고민한다.
– 문제 해결 시 다양한 접근 방법을 고려하면 더 효율적인 해결책을 찾을 수 있다.
