[파이썬] 백준 2309 일곱 난쟁이 풀이 2가지

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

2309번: 일곱 난쟁이

 

보고 재귀(dfs)로 푸는 방법밖에 생각이 안나서

이게 왜 브론즈....? 했던 문제

근데 알고보니 쉽게 푸는 방법이 있었고...

 

일단 dfs(재귀)로 푸는 방법부터...

난쟁이 7명을 뽑고, 순서는 상관 없고, 난쟁이는 한번씩 뽑하기 때문에 조합 문제이다.

arr = []
for i in range(9):
    n = int(input())
    arr.append(n)
path = [0]*7

def recur(level, start, total):
    global path

    if level==7:
        if total==100:
            path.sort()
            # path = sorted(path, key=lambda x:x)
            for i in range(7):
                print(path[i])
            quit()
        return

    for i in range(start, 9):
        path[level]=arr[i]
        recur(level+1, i+1, total+arr[i])

recur(0, 0, 0)

재귀함수에 start변수로 이미 갔던 곳 못가게 막아주고

total 변수도 써서 계산 편하게 해주기

 

 

하지만 dfs로 안풀어도된다.

arr = []
for i in range(9):
    n = int(input())
    arr.append(n)

for i in range(8):
    for j in range(i+1, 9):
        if sum(arr)-(s[i]+s[j])==100:
            fake1 = s[i]
            fake2 = s[j]

arr.remove(fake1)
arr.remove(fake2)

for i in arr:
    print(i)

remove를 array에서 바로 하면 나머지 숫자들의 인덱스도 바뀌기 때문에

새로운 변수에 넣어주고, 그 다음에 remove 하면 된다.