[프로그래머스-동적계획법] N으로 표현_파이썬 ❌❌

programmers.co.kr/learn/courses/30/lessons/42895?language=python3

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

---

def solution(N, number):
    dp = []
    
    for i in range(1, 9):
        numbers = set()
        numbers.add(int(i*str(N)))
        
        for j in range(i-1):
            for x in dp[j]:
                for y in dp[i-j-2]:
                    numbers.add(x+y)
                    numbers.add(x*y)
                    numbers.add(x-y)
                    if y != 0:
                        numbers.add(x//y)
        
        if number in numbers:
            return i
        
        dp.append(numbers)
    
    return -1

dp[i]는 N을 i + 1개 사용했을 때 만들 수 있는 값들이다.

N은 최대 8번 쓸 수 있으니 range(1, 9)로 for문을 돈다. i는 사용한 N의 개수를 뜻한다.

예를 들어보자. i가 4일 때 네 가지 경우가 가능하다. 

1. N을 연속으로 쓰는 경우(NNNN)
2. N(N을 한 번 썼을 때 나오는 수들, dp[0])과 NNN(N을 세 번 썼을 때 나오는 수들, dp[2])을 사칙연산 하는 경우
3. NN(dp[1])과 NN(dp[1])을 사칙연산 하는 경우
4. NNN(dp[2])과 N(dp[0])을 사칙연산 하는 경우

만약 numbers 안에 number가 있다면 i를 return한다.

for문을 다 돌고나서도 number를 찾지 못했다면 불가능한 것이므로 -1을 return한다.

 

이해가 어렵다면 아래 블로그를 참고.

gurumee92.tistory.com/164