백준 23842

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

23842번: 성냥개비

 

N = int(input())

#1부터 0까지 사용되는 성냥개비 수
numbers = [6,2,5,5,4,5,6,3,7,6]

def dfs(arr,idx,cnt):
  
  if idx==6 or cnt<0:
    if cnt==4  and arr[0]*10+ arr[1] + arr[2]*10 + arr[3] ==arr[4]*10 + arr[5]:
      print(str(arr[0]) + str(arr[1])+'+'+str(arr[2]) + str(arr[3]) + '=' +str(arr[4]) + str(arr[5]))
      exit()
    return
    
  for i in range(10):  
    arr[idx] = i
    dfs(arr,idx+1,cnt-numbers[i])
    arr[idx] = -1

dfs([-1]*6,0,N)

print('impossible')

 

dfs를 이용하여

깊이가 4까지 갔을 때

 

ㅁㅁ+ㅁㅁ=ㅁㅁ 형태를 만족하고 성냥의 개수를 만족하는 숫자를 출력