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

출처 : 백준, https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

 

백설 공주는 키 합이 100이면 누가되든 상관이 없던걸까?

백설 공주에게 난쟁이란 그런 언제든지 대체 가능한 존재였던걸까... 너무 불쌍해

 

보자마자 N-Qeeuns 문제가 떠올랐다.

 

참고 : 

Recursion(재귀)

Covenant님 블로그 - 용감하게 시작하는 코딩테스트 1편

 

 

풀이

 

Recursion와 Backtracking을 이용해서 문제를 해결해보자.

 

Backtracking을 이용하는 Recursion 함수의 대표적인 구조는 다음과 같다.

 

// 1. function이라는 함수가 호출된 순간을 상태공간트리의 노드에 도착한 순간이라고 생각
return-type function(arguments){ // 2. 매개 변수는 내가 어떤 노드에 도착했는지 확인할 수 있는 정보가 주어져야한다.
  // 3. 노드에 도착하면 해야할 일들
  if non-promising // 3-1. 노드가 꽝인가?
    report failure or return;
  else if success // 3-2. 내가 찾는 노드인가?
    report answer and return;
  else // 3-3. 꽝도 아니고 답도 아닌가?
    visit children recursivley;
}

 

위는 C언어의 형식이기 때문에 이를 파이썬 형식으로 바꾸면 다음과 같다.

 

def solution(arr, index):
  if non-promising:
    report failure and return false
  elif correct:
    report success and return true
  else:
    recursivly child node

 

이를 하나씩 채워나가자.

 

 

1. function이라는 함수가 호출된 순간을 상태 공간트리의 노트에 도착한 순간이라고 생각

 

재귀로 배열의 값을 하나씩 더해가면서 100이 되면 return True하는 알고리즘을 생각해보았다.

input으로 들어오는 난쟁이는 언제나 9명이므로 9번 받는다.

 

if __name__ == '__main__':
  dwarfs = []

  for i in range(9):
    dwarfs.append(int(input()))

 

좀 더 깔끔하게 작성한다면 이렇게 적을 수도 있겠다.

 

if __name__ == '__main__':
  dwarfs = [int(input()) for _ in range(9)]

 

 

2. 매개 변수는 내가 어떤 노드에 도착했는지 확인할 수 있는 정보가 주어져야한다. (매개변수 return 값 정립)

 

내가 어떤 노드에 도착했는지는 곧 내가 전체에서 몇번째 난쟁이가 진짜 난쟁이인지 아닌지 판별하는지와 같다.

그래서 배열과 현재의 배열 index를 매개변수로 주기로 했다.
그리고 생각해보니 7명을 더해야하기 때문에 현재까지 몇 명을 더했는지에 대한 정보도 나와야한다.
이는 global 변수인 stack에 쌓아서 len(stack)으로 계산하면 되겠다고 생각이 들어 stack 변수를 따로 선언해준다.

 

stack = []

def solution(arr, index):
  if non-promising:
    report failure and return false
  elif correct:
    report success and return true
  else:
    recursivly child node

 

 

3. 노드에 도착해서 해야할 일들

 

노드에 도착하면 먼저 전체 배열과 판별 대상인 난쟁이의 index가 주어져있다.

stack의 길이와 합으로 포함 여부를 판별을 할 것이므로 L과 S로 미리 선언해놓았다.

 

stack = []

def solution(arr, index):
  L = len(stack)
  S = sum(stack)  
  
  if non-promising:
    report failure and return false
  elif correct:
    report success and return true
  else:
    recursivly child node

 

 

3-1. 노드가 꽝인가?

 

만약 7명을 더했는데 합이 100이 되지 않는다면 return False를 한다.

이를 체크하는 promising 함수는 stack의 길이가 7일 때, stack 값들의 합이 100이 안된 것이다.

 

stack = []

def solution(arr, index):
  L = len(stack)
  S = sum(stack) 
  
  if L == 7 and S != 100:
    return False
  elif correct:
    report success and return true
  else:
    recursivly child node

 

 

3-2. 노드가 정답인가?

 

만약 7명을 더했는데 합이 100이 된다면 return True를 한다.

 

stack = []

def solution(arr, index):
  L = len(stack)
  S = sum(stack) 
  
  if L == 7 and S != 100:
    return False
  elif L == 7 and S == 100:
    return True
  else:
    recursivly child node

 

 

3-3. 노드가 정답도 꽝도 아니라면?

 

이 부분이 가장 어려운데 천천히 생각해보자.

stack에 7명보다 많은 수가 들어갈 수는 없다.

난쟁이를 하나씩 선택하면서 이 난쟁이가 맞는지 재귀적으로 호출하는 것이 else에서 할 일이다. (for : solution())

먼저 일단 난쟁이를 stack에 넣어야한다. 

난쟁이를 넣을 때 for 문을 사용해서 난쟁이를 넣는데, (stack.append(arr[인덱스]))

항상 처음부터 배열을 돌면 이미 지나온 난쟁이를 판별하게되므로

index 다음부터 끝까지 배열을 돈다. (for i in range(index + 1, len(arr))

돌 때, 만약 난쟁이가 최종 난쟁이가 맞다면 배열을 돌 필요가 없으므로 break한다. (if solution(arr, i): break)

아니라면 배열을 돌 필요가 있으므로 stack에서 pop하고 다음 난쟁이를 선택한다. (stack.pop)

 

stack = []

def solution(arr, index):
  L = len(stack)
  S = sum(stack)  
  
  if L == 7 and S != 100:
    return False
  elif L == 7 and S == 100:
    return True
  else:
    for i in range(index + 1, len(arr)):
      stack.append(arr[i])
      
      if solution(arr, i):
        break
      
      stack.pop()

 

 

최종 코드

 

main에 출력 코드를 더해 최종 함수를 완성한다.

또 solution의 매개변수 index에 기본값으로 -1을 지정하여 arr만 적어 호출할 수 있도록 만들었다.

index를 적어주며 호출하려면 solution(arr, -1)로 호출하여야한다.

 

stack = []

def solution(arr, index=-1):
  L = len(stack)
  S = sum(stack)
  
  if L == 7 and S != 100:
    return False
  elif L == 7 and S == 100:
    return True
  else:
    for i in range(index+1, len(arr)):
      stack.append(arr[i])
      
      if solution(arr, i):
        break
      
      stack.pop()
  
if __name__ == '__main__':
  dwarfs = [int(input()) for _ in range(9)]

  solution(dwarfs)
  
  for dwarf in sorted(stack):
    print(dwarf)

 

---

 

시간 복잡도

 

-

 

다른 사람의 풀이를 보면서 알게 된 점

 

-

 

고찰

 

학습했던 재귀를 이용해서 차근차근 풀어본 문제이다.

Backtracking이 필요한 재귀(혹은 DFS) 문제에서의 사고 방식을 저렇게 가져가려고 노력 중인데

처음이라 조금 어려웠지만 그래도 체화되면 재귀함수를 짜기 편해질 것 같다.