[백준] 2309번, 일곱난쟁이 (Python)

문제

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

2309번: 일곱 난쟁이

 

코드

height = [int(input()) for _ in range(9)]
total = sum(height)
for i in range(9):
    for j in range(i+1, 9):
        if total - (height[i] + height[j]) == 100:
            h1, h2 = height[i], height[j]
            height.remove(h1)
            height.remove(h2)
            break
    if len(height) < 9:
        break
height.sort()
for i in height:
    print(i)

9개의 입력값들이 주어지고 일곱난쟁이의 키의 합은 100이므로

9개의 입력값들을 전부 더한다음에 두개의 값을 뺏을때 100이 되면 남은 7개의 값이 일곱난쟁이의 키가 된다.

 

h1, h2에 값을 저장하는 이유는 한개의 height 리스트에서 값을 지웠을경우 인덱스에 값이 달라지기 때문에 값을 저장해둔다.

그런다음 pop() 대신에 리스트에 값으로 지울 수 있는 remove를 사용해주면 된다.

 

len(height)가 9보다 작은 경우는 두개의 값을 뺴고난 다음이므로 맨 처음 for문도 빠져나가주면된다.

 

재귀 풀이

height = [int(input()) for _ in range(9)]
check = [False] * 9
result = []
def recursive(index):
    global result
    if index == 9:
        answer = 0
        count = 0
        demo = []
        for i in range(9):
            if check[i]:
                answer += height[i]
                count += 1
                demo.append(height[i])
        if answer == 100 and count == 7:
            demo.sort()
            result = demo
        return
    
    check[index] = True
    recursive(index + 1)

    check[index] = False
    recursive(index + 1)

recursive(0)
for i in result:
    print(i)