[DFS/BFS/완전탐색] 2309번 - 일곱 난쟁이(DFS/완전탐색)

[백준] 2309번 - 일곱 난쟁이

풀이 시간: 10~15분 이내

9난쟁이 중에 키의 합이 100이 되는 7난쟁이를 구하는 문제로 조건에 맞는 조합을 구하는 전형적인 완전탐색 문제다. 그냥 for문으로 풀거나 DFS를 이용하여 풀거나 combinations 라이브러리를 이용하여 풀 수 있다. for문으로 푸는 방식이 가장 간편한 방식인 것 같다.

정답은 오름차순으로 출력해야하므로 입력받은 값(arr)을 오름차순 정렬하고 시작하면 무조건 출력은 오름차순 형태가 된다.

(풀이1) DFS 이용

1) 문제 해결 아이디어

<검사수 줄이는 방법>

1. 찾음 여부 확인

정답이 여러가지인 경우에는 아무거나 출력하라고 했으므로 정답을 찾으면 찾음 여부(find)를 True로 바꾼 후 해당 목록(temp)를 출력한다. 그리고 찾음 여부(find)가 False일 때만 dfs에서 선택을 진행하도록 한다.

2. depth이후 값의 범위에서 선택

순열이 아닌 조합을 구하는 문제이기 때문에 for문에서 항상 0부터 시작할 필요가 없고 i번쨰 값을 선택할 때 depth이후 범위에 대해서 선택할 수 있도록 한다.

 

2) 소스코드

# 9 난쟁이의 키
arr = [(int(input())) for _ in range(9)]
arr.sort()  # 오름차순 정렬
temp = []   # 7 난쟁이 목록
find = False  # 찾음 여부

# DFS
def dfs(depth):
  global find
  # 답을 찾았으면 바로 종료
  if find: return
  # 7 난쟁이를 다 선택했다면
  if(depth == 7):
    # 키의 합이 100이면
    if sum(temp) == 100:
      for i in temp:
        print(i)
      find = True    # 찾음으로 변경
    return
  # 7 난쟁이를 다 선택하지 않았다면
  else:
    # depth 이후 값의 범위에서 선택
    for i in range(depth, len(arr)):
      # 선택하지 않았던 수라면
      if arr[i] not in temp:
        temp.append(arr[i])
        dfs(depth + 1)
        temp.pop()

dfs(0)

 

풀이 시간: 20분 이내

(풀이2) for문 이용

1) 문제 해결 아이디어

7난장이를 찾기 위해 7중 for문을 돌릴 수는 없으므로 역으로 전체합(total) - 2난장이의 합이 100이 되는 2난장이를 찾아 리스트에서 제거하는 방식으로 구현하였다. 

 

2) 소스코드

arr = [(int(input())) for _ in range(9)]
res = sorted(arr)   # 7난장이
find = False  # 찾음 여부
total = sum(arr)  # 9난장이 합

for i in range(8):
  # 찾으면 종료
  if find:  break
  for j in range(i + 1, 9):
    # 2난쟁이를 뺀 7난쟁이의 합이 100이면
    if total - arr[i] - arr[j] == 100:
      # 2난쟁이 제거
      res.remove(arr[i])
      res.remove(arr[j])
      find = True
      break
      
for i in res:
  print(i)

[참고] https://ywtechit.tistory.com/133

[ 파이썬(python) ] 백준 2309 - 일곱 난쟁이