[프로그래머스 스터디 6주차] 동적계획법 N으로 표현 Lv.3 - 파이썬(Python)/ DP

📑 문제

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

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

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

 

 

 

 

 

 

 

 

 

✒️ 풀이

 DP 메모이제이션을 사용하는 문제이다. 

 number를 만들기 위해 N을 최소로 사용해야 한다. 그러려면, N을 1번 썼을 때부터 2번, 3번...늘려가며 모든 연산을 처리했을 때 number가 나오는지를 체크하고 멈춰야 한다.

 

✔️ dp[ i ] : N을 i번 썼을 때 만들어지는 숫자 조합

 

◻️ N을 1번~9번 사용하는 모든 경우를 따져본다.

◻️ K번 사용하는 경우는, 1~(K-1)번 썼을 때 나오는 숫자에 (K-1)~1번 썼을 때 나오는 숫자를 이어붙이는 것이다.

     ex) N을 4번 사용한 경우는 다음과 같다. dp[1]🔁dp[3] / dp[2]🔁dp[2]/ dp[3]🔁dp[1]

◻️ 따라서 K번 사용하는 경우를 위해 dp[1]🔁dp[K-1], dp[2]🔁dp[K-2] ...를 하나하나 연산한 후 중복방지를 위한 집합에 결과를 추가한다.

◻️ 모든 조합을 다 마친 후 number가 결과집합 안에 들어있다면, 바로 K를 리턴하고 연산을 종료한다.

 

 

 

 

 

 

 

🙋‍♀️ 의견

 DP는 해도해도 모르겠다....그래도 이 문제가 감을 잡는데 도움이 크게 되는 것 같다.

 

 

 

 

 

 

 

💻 소스코드: 파이썬(Python)

def solution(N, number):
    answer = -1
    dp = [0]

    # N을 1번 사용-> N
    # N을 2번 사용-> NN, N-N, N+N, N*N, N/N
    for i in range(1, 9): #N을 i번 사용해서 만드는 숫자조합 찾기 
        num_set = set()
        num_set.add(int(str(N)*i))

        for j in range(1, i): #예를 들어 i가 6이고 j가 2라 할 때
            for x in dp[j]: # dp[2]
                for y in dp[-j]:  # dp[-2] = dp[4]
                    num_set.add(x + y)
                    num_set.add(x - y)
                    num_set.add(x * y)

                    if y != 0:
                        num_set.add(x // y)

        if number in num_set:
            return i
        dp.append(num_set)
    return answer


#예제 출력
#print(solution(5, 12))
#print(solution(2, 11))

 

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨