(Python/LV3) N으로 표현

문제 출처: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