[백준] 2309 일곱난쟁이 / 파이썬 (Python) / 3가지 풀이

https://www.acmicpc.net/problem/2309

입력 : 9줄로 난쟁이들의 키 입력

출력 : 오름차순으로 난쟁이 키 7줄 출력

 

sol 1: 조합 사용

처음 생각한 방식은 9명 중에 7명 조합을 모두 구해서 해당 조합들의 합이 100이 되는 경우를 출력하는 것이다.

알아야 하는 것 : 파이썬에서 조합 사용(itertools)

from itertools import combinations
k = sorted([int(input()) for _ in range(9)])

# 7명 경우의 수 찾기 : 조합
com_list =list(combinations(k, 7))

for i in com_list:
    ans = sum(i)
    if ans == 100: # 해당 조합의 키의 합이 100이면
        # print(i) 튜플 형태로 출력
        for j in i:
            print(j)
        break

출력을 오름차순으로 해야하기때문에, 입력 받을때부터 리스트 자체를 오름차순으로 받았다.

간단한 문제라 이렇게 받아도 되겠지만, 숫자가 많아지면 안될 것 같다.

 

sol 1-1: 조합 사용하지만 2명씩 조합

조합을 사용 안하고 풀려다 또 조합을 사용했다...

이번 방식은 9명 중에서 7명의 조합을 찾는게 아니라 2명의 조합을 찾는다.

애초에 난쟁이는 7명, 키의 합이 100이라고 정해져있기때문에, 2명은 무조건 가짜다.

그 가짜는 9명 전체 키의 합 - 100을 한 2명의 조합이다.

1 전체 합 - 100 인 2명 찾기

2 그 2명 빼고 나머지 7명 출력하기

from itertools import combinations

k = list(int(input()) for _ in range(9))

# 9명 전체 키의 합
total_height = sum(k)

# 전체 키의 합 - 100인 2명 조합 찾기
for i in combinations(k,2):
    if sum(i) == total_height - 100:
        fake_list = list(i)
        break

# 가짜 난쟁이를 리스트에서 삭제
for x in fake_list:
    k.remove(x)

# 진짜 난쟁이들 오름차순 출력
for height in sorted(k):
    print(height)

sol 2 : 브루트포스 (이중반복문)

라이브러리를 사용하지 않고 이중반복문으로 완전 탐색해서 풀이

k = [int(input()) for _ in range(9)]
total_height = sum(k) # 난쟁이 전체 키의 합

# 가짜 두 명
f1, f2 = 0, 0

# 이중반복문 사용
for i in range(8):
    for j in range(i + 1, 9):
        if k[i] + k[j] == total_height - 100:
            f1, f2 = k[i], k[j]
            break
    if f1 != 0:
        break

k.remove(f1)
k.remove(f2)

for i in sorted(k):
    print(i)

 

sol 3 : 백트래킹 (재귀)

# 백트래킹

# 종료조건 : 선택한 난쟁이가 7명이고, 그 합이 100일때
def find(index, selected):
    if len(selected) == 7:
        if sum(selected) == 100:
            for num in sorted(selected):
                print(num)
            exit()
        return

    # 모든 난쟁이 탐색 시 종료
    if index >= 9:
        return

    # 현재 난쟁이를 선택하는 경우
    find(index + 1, selected + [k[index]])
    # 현재 난쟁이를 선택하지 않는 경우
    find(index + 1, selected)

k = [int(input()) for _ in range(9)]

find(0, [])

1 함수 정의

find(index, selected)

- index : 현재 탐색할 난쟁이의 위치 (0 ~ 8)

- selected : 지금까지 선택된 난쟁이들 (리스트)

 

2 종료 조건

selected 리스트의 길이가 7일때, 그 합이 100인 경우, 오름차순으로 정렬 후 출력 (정답)

모든 난쟁이들을 탐색했을 경우 종료

 

3 재귀 호출

현재 난쟁이를 포함하는 경우, 현재 난쟁이를 포함하지 않는 경우 재귀함수로 호출 (모든 조합을 보기 위해서!)

 

시간복잡도

조합과 이중반복문은 O(1)이지만 백트래킹은 최악의 경우 O(2의 9제곱)이므로 이중반복문과 조합이 가장 효율적이라고 할 수 있다.