프로그래머스 N으로 표현 파이썬

https://programmers.co.kr/learn/courses/30/lessons/42895

코딩테스트 연습 - N으로 표현

 

 

DP문제라고 말 안듣고 시작했으면 평생 못풀었을거같읍니다

 

RETURN값이 8을 넘지 않기 떄문에

[5],[55],[555] ~~ [55555555] 까지 있는데

EX RETURN 2) [(55),(5-5),(5+5),(5*5),(5/5)] 사칙연산 + (숫자를 붙여놓음)을 다 넣으면된다.

 

이걸 모든 경우를 다 때려박으면 된다.

 

RETURN = 1 [5]

RETURN = 2 [0,1,10,25,55]

RETURN = 3 ((RETURN 2)과 RETURN 1) 에 대한 사칙연산

RETURN = 4 (RETURN~3까지 ) 에 대한 사칙연산

FOR문을 8까지 진행 이후에도 NUMBER 과 동일한 값이 안나온다면 -1

 

만약 나왔다면 현재 진행중인 RETURN 값 반환

 

 

def solution(N, number) :
    answer = 0

    if N == number :
        return 1

    s = [set() for i in range(8)]

    for i in range(1,9):
        s[i-1].add(int(str(N)*i))

    for i in range(1,8):
        for j in range(i):
            for x in s[j]:
                for y in s[i-j-1]:

                    s[i].add(x+y)
                    s[i].add(x-y)
                    s[i].add(x*y)
                    if y != 0 and x != 0:
                        s[i].add(x//y)

        if number in s[i]:
            answer = i+1
            break

    if answer == 0:
        answer = -1

    return answer