[프로그래머스] - N으로 표현 with Python

💡문제 설명

아래와 같이 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 합니다.

입출력 예

 

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

 

 

프로그래머스 - N으로 표현 

프로그래머스

 

---

🙆🏻‍♀️ How to Solve 

이 문제는 DP로 접근해야한다.

 

문제의 예시처럼 N을 5라고 해보자. 

5를 1번 사용할 때 => {5}

5를 2번 사용할 때 => 1번과 1번을 활용하여 사칙연산 =>  {55, (5+5), (5*5), (5/5), (5-5)}

5를 3번 사용할 때 => 1번과 2번을 활용하여 사칙연산 => {555, 5+(5+5), 5*(5+5), 5/(5+5), 5-(5+5), 5+(5*5), 5*(5*5), 5/(5*5), 5-(5*5), 5+(5/5), 5*(5/5), 5/(5/5), 5-(5/5), .....}

5를 4번 사용할 때=> 1번과 3번, 또는 2번과 2번을 활용하여 사칙연산 

.

.

.

이런식으로 이전에 저장해두었던 dp[i]값을 활용하여 n을 i번 사용할 때의 횟수를 구할 수 있다. 

 

이런식으로 n을 사용하는 횟수를 늘려갈 때마다 number값이 집합안에 있는지 확인하고 있으면 return값으로 dp[i]의 i를 반환한다. 

 

 

 

💻 Code 

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

1. 먼저 dp[]에 N(1~8)사용횟수에 따라 저장할 수 있는 집합 set을 만든다.
(set을 사용하는 이유는 중복을 제거하고 , in 탐색에 있어 효율적이기 때문) 
2. 다음 각각의 횟수만큼 이어진 문자열을 집합에 넣는다. - {5}, {55}, {555}, ...
3. 예를 들어 i가 5라면 5가 되는 수 (1,4), (2,3)을 찾기 위해 for문으로 first, second값을 찾는다. 
4. 찾은 뒤 first와 second값을 가지고 사칙연산을 수행한다.  
5. 만약 집합 안에 number 값이 존재한다면 i가 n을 사용한 횟수이므로 i 값을 반환.
6. 8보다 크면 -1반환