백준 : 2309 일곱 난쟁이

문제 내용

간단하게 생각하면 9명의 난쟁이에서 7명을 무작위로 선택했을 때, 난쟁이 키의 총 합이 100 인 경우의 수를 구하면 된다.

조합의 원리로, 난쟁이 키가 100인 경우는 9C7 으로 총 36개의 조합이 나온다.

여러모로 삽질을 했지만, 사실 가장 쉽게 푸는 방법은 combinations 라이브러리를 이용하는 것 이었다. 9개중 7개의 숫자를 추출해서, 합이 100이되는 첫 조합을 리스트로 반환하여 출력한다.

from itertools import combinations

a = [int(input()) for __ in range(9)]
a.sort()
for comb in combinations(a, 7):
    if sum(comb) == 100:
        c = list(comb)
        
for c in c :
    print (c)

 

처음에는 더하는 것만 생각했는데, 조합의 원리를 깨닫고 9개에서 2개를 빼는 방향으로 for문을 구성해보았다. 이부분은 무한한 검색의 결과를 참조하여 코드를 작성할 수 있었다.

a = [int(input()) for __ in range(9)]
a.sort()

for i in range(len(a)):
    for j in range (i+1, len(a)):
        if sum(a) - a[i] - a[j] == 100:
            for k in range (len(a)):
                if k == i or k == j:
                    continue
                else:
                    print(a[k])
            exit()

 

사실 이 문제에서 제일 구현하고 싶었던 부분은 재귀 함수를 이용하여, 2가지를 제외하는 방법으로 풀이하고 싶었다. 아래 코드는 백준에서 패스를 받지 못하여, 우선 다음날의 과제로 두겠다. 재귀 함수 너무 어렵다.

패스를 받지 못한 원인은, 아무래도 조합이 항상 7개를 유지하지 않고 있는것 같다. 추가 디버깅을 해봐야겠다.

a = [int(input()) for __ in range(9)]

def reverse (a, start, removed_count):
    if removed_count == 2:
        if sum(a) == 100:
            print(*a, sep="\\n")
            exit()
        return a
    
    for i in range (start, len(a)):
        reverse (a[:i]+a[i+1:], i, removed_count+1)

reverse (a, 0, 0)

 

2025-03-19 코드 수정

재귀함수로 백트래킹한 코드를 수정하여 백준 정답을 찾았다. 기존에 리스트 자체를 매번 새로 생성하면서 원래 리스트의 참조를 잃어버리는 문제가 발생할 수 있다. 즉 특정 요소를 제외한 후 i+1 기반으로 탐색하지 않으면 제거한 숫자 이후의 경우를 건너뛰게되고, 합이 100 인 경우를 찾을 수 없을 가능성이 있다.

 

이는 리스트 자체를 생성하지 않고, 제거할 값을 pop 연산 후, 재귀 함수를 호출하고, 호출이 완료되면 다시 넣는 방식으로 구현하여 해결되었다.

a = [int(input()) for __ in range(9)]

def reverse (a, start, removed_count):
    if removed_count == 2:
        if sum(a) == 100:
            print(*a, sep="\\n")
            exit()
        return a
    
    for i in range (start, len(a)):
        removed_value = a.pop(i)
        reverse (a, i, removed_count+1)
        a.insert(i, removed_value)
reverse (a, 0, 0)