[파이썬]백준 2309 일곱난쟁이

링크

백준 2309 일곱난쟁이

백트래킹으로 구현했다.
이번엔 가지치기를 시도했고 한번에 실패 끝에 성공했다.

오답 1

def perm(idx, j):
    global ans

    if sum(sel) > 100:
        return

    if idx == 7:
        if sum(sel) == 100:
            ans = sorted(sel)

    else:
        for i in range(j, 9):
            if visit[i] == 0:
                visit[i] = 1
                sel[idx] = dwarves[i]
                perm(idx + 1, j + 1)
                visit[i] = 0


dwarves = [int(input()) for _ in range(9)]
visit = [0] * 9
sel = [0] * 7
ans = []
perm(0, 0)
print('\n'.join(map(str, ans)))

가지치기를 위해 sum(sel) > 100 이라는 조건을 주니 자꾸 인덱스 에러가 났다.
해당 조건을 삭제하면 통과했으나 원하던 바가 아니라 해결을 위해 고민했다.
고민끝에 total변수를 하나 더 줘서 합을 계산하기로 했다.
근데 아직도 저게 왜 인덱스 에러가 나는지는 모르겠다..

정답 코드

def perm(idx, j, total):
    global ans

    if total > 100:
        return

    if idx == 7:
        if total == 100:
            ans = sorted(sel)

    else:
        for i in range(j, 9):
            if visit[i] == 0:
                visit[i] = 1
                sel[idx] = dwarves[i]
                perm(idx + 1, j + 1, total + dwarves[i])
                visit[i] = 0


dwarves = [int(input()) for _ in range(9)]
visit = [0] * 9
sel = [0] * 7
ans = []
perm(0, 0, 0)
print('\n'.join(map(str, ans)))

total 이라는 합을 계산하는 인자를 함수 넣어줘서 해당 인자를 활용해 가지치기를 했다.

알게된 것👨‍💻

• sum()으로 조건을 판단하기 보단 함수에 조건을 판단할 인자를 추가하자.