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

문제

 

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

프로그래머스

문제 설명

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

 

입출력 예

N	number	return
5	12	4
2	11	3

 

 

문제풀이 코드

def solution(N, number):
    answer = -1
    if N == number:
        return 1
    
    dp = [[] for _ in range(9)]
    
    # 최솟값이 8보다 클 수 없기때문에 1개부터 8개까지 N으로 만들 수 있는 모든 수를 구한다.
    for i in range(1, 9):
    	# 숫자 이어 붙이기
        dp[i].append(int(str(N) * i))
        for j in range(1, i):
            for num1 in dp[j]:
                for num2 in dp[i - j]:
               	    # 사칙연산
                    dp[i].append(num1 + num2)
                    dp[i].append(num1 * num2)
                    dp[i].append(num1 - num2)
                    if num2 != 0:
                        dp[i].append(num1 // num2)
        if number in dp[i]:
            answer = i
            break
    return answer

동적 계획법으로 문제 풀이

1. N = 5일 때, 5를 만들기 위해서는 5가 1개 있으면 되기 때문에  dp[1] = [5]가 된다. 

2. 5가 2개 있으면 만들 수 있는 수는 [0, 1, 10, 25, 55]이다. 

3. 5가 3개 있으면 만들 수 있는 수는[0, 2, ... 555]가 있다.

4. 이를 통해 알 수 있는 것은 dp[3] = dp[1] ㅇ dp[2], dp[2] ㅇ dp[1]이 된다. (ㅇ 는 사칙연산을 표현)

5. dp[4] = dp[1] ㅇ dp[3], dp[2] ㅇ dp[2], dp[3] ㅇ dp[1]이 되게 된다.

6. 이를 통해 점화식을 도출하면, dp[i] = dp[j] ㅇ dp[i-j] 가 된다.

7. 이제 반복문을 돌면서 1개부터 9개 까지 N으로 만들 수 있는 모든 수들을 구하여 찾고있는 수가 dp에 들어있을 때 i값을 반환하면 된다.