프로그래머스_N으로 표현

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 합니다.

입출력 예

N	number	return
5	12	4
2	11	3

입출력 예 설명

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

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

concept

동적 계획법 -> 전에 사용했던 데이터를 저장하여 이후에 재사용하는 알고리즘.

이 문제에서는
case1 주어진 숫자를 한 개 사용하여 만들 수 있는 경우 [5]
case2 주어진 숫자를 두 개 사용하여 만들 수 있는 경우 [55, 5/5, 5*5, 5+5, 5-5]
case3 주어진 숫자를 세 개 사용하여 만들 수 있는 경우 [555, 55/5, 555, 55+5, 55-5, 5/55, 555, 5+55, 5-55, 5+5+5, 5-5-5, 555, 5/5/5 .. ]
등등..

case1 = case1
case2 = case1 & case1
case3 = case1 & case2 | case2 & case1
로 생각할 수 있다..

주의점 : case3 = case1 & case1 & case1 아닌가라는 생각은 case1 & case2(case1+case1)으로 이미 포함되어 있다

...

한 단계씩 증가할 때마다 이전 단계의 결과값을 재사용하는 것을 확인할 수 있다.. like 점화식

code

def solution(N, number):
    answer = -1
    dp = []
    #1~8개의 케이스
    for i in range(1,9):
        #중복인 경우 제외 처리
        all_case = set()
        duple_number = int(str(N)*i)
        all_case.add(duple_number)
        #dp에 저장되어 있는 값들을 활용
        #i = 2 -> 1+1
        #ex) i=4 -> 1+3(0,2), 2+2(1,1), 1+1+2(0,0,1)
        #i = 5 -> 1+4(0,3), 2+3(1,2)
        #i = 6 -> 1+5(0,4), 2+4(1,3), 3+3(2,2)
        for j in range(i-1):
            for num1 in dp[j]:
                for num2 in dp[i-j-2]:
                    all_case.add(num1 + num2)
                    all_case.add(num1 - num2)
                    all_case.add(num1 * num2)
                    if(num2 != 0):
                        all_case.add(num1 // num2)
        if(number in all_case):
            return i
        
        dp.append(all_case)
        
    return answer

참고

• 전에 사용된 결과를 담을 dp배열이 필요
• 중복을 제거하기 위하여 set()처리
• '*', '+'연산은 상관없지만, '/' '-'연산은 순서에 따라 결과 값이 바뀌기 때문에 대칭적으로 모두 돌아야한다.
• 코딩을 시작하기전에 사용된 값이 재사용된다면 점화식을 먼저 세워보는것도 좋을듯..!