728x90
반응형
문제 출처:https://school.programmers.co.kr/learn/courses/30/lessons/42895
풀이:
def solution(N, number):
if number == N:
return 1
list =[set() for i in range(8)] # 최솟값이 8 이기 때문
for i in range(len(list)):
list[i].add(int(str(N)*(i+1)))
for i in range(1,8):
for j in range(i):
for op1 in list[j]:
for op2 in list[i-j-1]:
list[i].add(op1+op2)
list[i].add(op1-op2)
list[i].add(op1*op2)
if op2 != 0:
list[i].add(op1//op2)
if number in list[i]:
answer = i+1
break
else:
answer = -1
return answer
print(solution(5,12))
list =[set() for i in range(8)] # 최솟값이 8 이기 때문
for i in range(len(list)):
list[i].add(int(str(N)*(i+1)))
set으로 중복되는 숫자 걸러주고 각 set에 N * 갯수만큼 넣어준다
{5}, {55} ...
for i in range(1,8): # 0번째는 5 하나로 이미 끝났기때문에 1번째부터 5+5/5-5 등이 필요하기때문 1부터한다
for j in range(i): # 만약 i가 3이면 2까지 해야 3번째 list에 넣을수있음
for op1 in list[j]: # op1이 0이면
for op2 in list[i-j-1]: #op2는 3이다
list[i].add(op1+op2)
list[i].add(op1-op2)
list[i].add(op1*op2)
if op2 != 0:
list[i].add(op1//op2)
5의 갯수를 생각하면 되는데
만약 i가 0 이고 j가 3이면 list[0] 에는 5가 1개 짜리 연산 list[3] 에는 5가 4개짜리연산이 들어있다.
이 두개를 더해면 5가 5개짜리 연산인것이다.
만약 5를 4개를 사용한 list[3]을 알고 싶으면
list[0] +list[2] // list[1] +list[1] / list[2] +list[0] 이런식으로 나와야하기때문에
마지막 포문에 [i-j-1] 을 해준 이유다 -1 을 안 해주면 5의 개수가 초과로 사용됨
op2 != 0 은 op2 = 0 이면 0으로 나눌수 없는 에러가 나온다.
if number in list[i]:
answer = i+1
break
찾는 숫자가 있으면 0번째 부터이니깐 +1
else:
answer = -1
없으면 -1
반응형
댓글