[동적계획법(Dynamic Programming)] N으로 표현

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

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

 

 

 

처음에 아래와 같이 푸니까, 테스트케이스 5, 6, 7 다 틀려서  ..??? 했는데

 

이전 결과에 N연산만 하는 것이아니라, 숫자 4개의 조합의 경우

(3개로만들수있는경우 * 1개로만들수있는경우) , (2개로만들수있는경우 * 2개로만들수있는경우) 와 같이 모두 경우를 추가해줘야한다.

 

 

- 코드

def solution(N, number):
    cases = {}
    if N==number:
        return 1
    cases[1] = set({N})
    for i in range(2, 9):
        temp = [int(str(N)*i)]
        for c_half in range(1, i//2+1):
            for x in cases[c_half]:
                for y in cases[i-c_half]:
                    taemp.append(x*y)
                    temp.append(abs(x-y))
                    temp.append(x+y)
                    if x!=0 and y!=0:
                        temp.append(x//y)
                        temp.append(y//x)
        if number in temp:
            return i
        cases[i] = (set(temp))
    return -1

성공!