N으로 표현 - Python, DP

 

 

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

프로그래머스

 

 

풀이 - 나의 생각

 

DP는 진짜....

 

다들 정규식을 어떻게 생각하는지 신기하다.

 

이 문제의 경우는

 

dp[2] 는 dp[1]에서 사칙연산한 결과이다.

 

dp[3]는 그러면 dp[1]과 dp[2]를 조합한 결과인 것이다.

 

그 이후도 다 똑같은 방식이다.

 

dp[i]는 i 이전의 dp들의 조합의 결과인 것이다.

 

 

 

코드

 

def solution(N, number):
    if N == number:
        return 1
    
    # 최대 8까지만 가능
    dp = [set() for _ in range(9)]
    dp[1].add(N)
    
    for i in range(2, 9):
        dp[i].add(int(str(N) * i))  # N, NN, NNN 등 생성
        
        for j in range(1, i):
            for op1 in dp[j]:
                for op2 in dp[i - j]:
                    dp[i].add(op1 + op2)
                    dp[i].add(op1 - op2)
                    dp[i].add(op1 * op2)
                    if op2 != 0:
                        dp[i].add(op1 // op2)

        if number in dp[i]:
            return i
    return -1

 

 

 

 

 

 

 

다음에 또 봐요