Jungle

2309 일곱 난쟁이

TIL-0710(Jungle)

1. 문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

출력

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

2. 풀이

코드

heights = [] # 키 받을 리스트
# 9명 입력받고 리스트에 저장
for _ in range(9):
    height = int(input())
    heights.append(height)
    
total = 0 # 키의 합
for height in heights:
    total += height

# (0,1) 부터 (7, 8)까지의 모든 경우의 수 생성
for i in range(8): # 0~7
    for j in range(i + 1, 9): # 1~8
        # 전체 키에서 두명의 키를 뺐을때 100이면 나머지가 진짜 난쟁이
        if total - heights[i] - heights[j] == 100:
            real_dwarfs = [] # 진짜 난쟁이 담을 리스트
            for h in heights: 
                # 키 리스트에서 가짜 난쟁이 제외하고 진짜 난쟁이 리스트에 저장
                if h != heights[i] and h!= heights[j]:
                    real_dwarfs.append(h)

            # 키순서대로 정렬하기
            real_dwarfs.sort()
            
            # 출력
            for dwarf in real_dwarfs:
                print(dwarf)
            
            exit()

문제풀이

  1. 키 받을 빈 리스트 heights 생성

  2. 9명의 키를 입력받아 리스트에 저장

  3. 키의 합을 받을 변수 초기화 키들이 담긴 heights 리스트에서 하나씩 더해 키의 합 구하기

  4. 이중 for 루프:

    • for i in range(8): # 1~7 for j in range(i + 1, 9): # 1~8

    • 이중 for 루프를 돌면서 9명 난쟁이 중 2명을 선택하는 모든 가능한 조합 생성

    • 생길 수 있는 조합 - 9C2=36{}_{9}\mathrm{C}_{2} = 36

      (0,1), (0,2), ..., (0,8), (1,2), (1,3), ..., (7,8) 찾을 수 있음

    • for i in range(8): → 바깥 루프 i는 0~7까지 반복(총 8번 반복)

      for j in range(i + 1, 9): → 안쪽 루프 j 는 i+1 부터 8까지 반복

      왜 i+1을 하는가?

      중복 피하고 불필요한 계산 줄일 수 있음

      j가 항상 i보다 큰값을 가지게 됨

      • 같은 조합 2번 검사 X

      • (a,b)와 (b,a)와 같은 중복을 피하고 (a,a)와 같은 자기 자신과의 조합도 제외

  5. 조건 확인:

    if total - heights[i] - heights[j] == 100:

    전체 합 total에서 현재 선택된 두 난쟁이의 키(heights[i]와 heights[j])를 뺀 값이 0인지 확인

    → 참이면 선택된 두 난쟁이가 가짜일 수 있음

  6. 진짜 난쟁이 선별:

    • 진짜 난쟁이가 담길 빈 리스트 real_dwarfs 생성

    • 모든 난쟁이의 키(heights)를 순회하며, 현재 키(h)가 가짜로 의심되는 두 난쟁이의 키(heights[i]와 heights[j])와 다르면, 그 키를 real_dwarfs 에 추가

  7. 정렬 및 출력:

    real_dwarfs.sort()

    • sort()로 리스트 오름차순으로 정렬

      정렬된 리스트의 각 요소를 한줄에 하나씩 출력

  8. 프로그램 종료:

    exit() → 정답을 찾아 출력하면, 더 이상 탐색이 필요없으므로 프로그램 즉시 종료

수학적 설명

난쟁이 중 2명을 선택하는 조합(Combination) 문제

  • 조합의 표기:

    nCr{}{n}\mathrm{C}{r}로 표기하며, n개 중 r개를 선택하는 조합의 수

    n은 전체 원소의 수, r은 선택할 원소의 수

  • 이 문제에서의 조합:

    n=9n = 9(전체 난쟁이 수), r=2r = 2 (선택할 난쟁이 수)

    9C2=9!2!(9−2)!=9!2!7!=36{}{_9}\mathrm{C}{_2} = \frac{9!}{2!(9-2)!} = \frac{9!}{2!7!} = 36

  • 이중 for 루프와 조합의 관계: 바깥 루프 i는 0부터 7까지, 안쪽 루프 j는 i+1부터 8까지 반복합니다. ∑i=07(8−i)=8+7+6+5+4+3+2+1=36\sum_{i=0}^{7} (8-i) = 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36

  • 이 식은 각 i에 대해 j가 몇 번 반복되는지를 합한 것으로, 전체 조합의 수와 일치합니다.

코드의 이중 for 루프는 이 36가지 조합을 효율적으로 생성

외부 루프 i는 0부터 7까지, 내부 루프 j는 i+1부터 8까지 반복 → 중복 없이 정확히 36번의 반복 수행

3. 플로우차트

Reference

https://namu.wiki/w/조합

분류

브론즈 1

브루트포스 알고리즘

정렬

PreviousBrute force / 완전탐색Next2798 블랙잭

Last updated