[BOJ] 2309 - 일곱 난쟁이 (🥉 브론즈 2티어)

사용 언어: Python3

문제

일곱 난쟁이

풀이

나의 풀이 - DFS

N, M = 9, 7
lst = [int(input()) for _ in range(N)]

# 9개중 7개 뽑기
def DFS(L, start):
    global flag
    if flag:
        return
    if L == M:
        if sum(res) == 100:
            for x in sorted(res): print(x) # ✅ 오름차순 정렬
            flag = True
    else:
        for i in range(start, len(lst)):
            res[L] = lst[i]
            DFS(L+1, i+1)

flag = False # ✅ 이미 정답 나왔으면 종료하기 위한 플래그
res = [0] * M # 선택된 일곱 난쟁이 키
DFS(0, 0)

• 테스트 케이스: 통과
• 제출 결과: 통과
  

다른 풀이 - 라이브러리 이용

from itertools import combinations

N, M = 9, 7
lst = [int(input()) for _ in range(N)]

# lst 에서 7개 뽑기
for x in combinations(lst, M):
    if sum(x) == 100:
        for val in sorted(x): print(val)
        break

• 테스트 케이스: 통과
• 제출 결과: 통과
  

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기