N으로 표현
from collections import defaultdict
from itertools import product
def solution(N, number):
if N == number : return 1
N_combinations = defaultdict(set)
calculations = ['+', '-', '*', '/']
for n in range(1, 9) :
N_combinations[n].add(int(str(N)*n))
for i in range(1, n) :
for x, sign, y in product(N_combinations[i], calculations, N_combinations[n-i]) :
if sign == '/' and y == 0 : continue
res = eval(str(x)+sign+str(y))
N_combinations[n].add(res)
if number in N_combinations[n] :
return n
return -1
N 몇개로 표현?
greedy하게 풀려고하는 나같은 흑우들이 있을까봐 친절하게 문제 종류까지 알려줬다. DP문제답게 접근해보면 N을 k-1개까지 써서 표현한 조합들로 N을 k개 써서 만들 수 있는 조합을 구할 수 있다는 말이다. 그리고 그중에 number가 있으면 N이 답이된다. 대신 k <= 8이라는 조건이 붙었다.
삽질
패턴이 도저히 안보일땐 그냥 몸으로 맞으면된다.
DP[1] = N
어차피 N하나로는 하나밖에 없다. 그렇다면 2개로 만들 수 있는 조합을 보면
DP[2] = NN, N+N, N-N, N/N, N*N
뭔가 느낌이 온다.
DP[3] = NNN, NN+N, NN-N, NN/N, NN*N N+NN, N+N+N, NN-N, NN/N, NN*N N-NN, N-N+N, N-N-N, N-N/N, N-N*N N*NN, N*(N+N), N*(N-N), N*N/N, N*N*N N/NN, N/(N+N), N/(N-N), N/(N/N), N/(N*N) NNN, N+NN, N-NN, N/NN, N*NN ...
DP[3] = DP[1]+DP[2], DP[2]+DP[1]
패턴을 찾음 ㅅㄱ. 그리고 *, / 이거 때문에 DP[1]+DP[2] != DP[2]+DP[1] 이렇게 된다는것도 파악할 수 있다(마치 행렬곱처럼).
DP[n] = DP[1]+DP[n-1] ,DP[2]+DP[n-2], ..., DP[n-1]+DP[1](+은 조합끼리의 덧셈)
N_combinations
N_combinations 사전을 만들어서 {조합숫자 : [조합계산한값들]} 이런식으로 꺼내서 쓸 예정이다. 조합을 넣지 않고 조합을 계산한 값을 넣는 이유는 어차피 저거 꺼내서 계산 할껀데 미리 계산해서 넣어주는거다.
from collections import defaultdict
from itertools import product
def solution(N, number):
if N == number : return 1
N_combinations = defaultdict(set)
calculations = ['+', '-', '*', '/']
for n in range(1, 9) :
N_combinations[n].add(int(str(N)*n)) # NNN.. 은 미리 계산
for i in range(1, n) : #인덱싱은 직접 해보면서 이해하셈
for x, sign, y in product(N_combinations[i], calculations, N_combinations[n-i]) : #DP[n-k] + DP[k]
#product : 카디션곱 모르겠으면 list(product(['1', '2'], ['+', '-'], ['3', '4'])) 돌려보셈
if sign == '/' and y == 0 : continue # 나누기할때만 분모가 0인지 검사
res = eval(str(x)+sign+str(y)) #eval은 str타입 다항식 계산해주는 메서드
N_combinations[n].add(res)
if number in N_combinations[n] :
return n
return -1