동적계획법 (Dynamic Programming) - N으로 표현** (Lv.3)

문제 설명

아래와 같이 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번만 사용하여 표현할 수 있습니다.

 

 

동적계획법
동적 계획법의 접근 방식은 기본적으로 분할 정복 알고리즘과 비슷한 것으로 주어진 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산하고, 이 계산한 결과값을 이용해 원래 문제의 답을 산출하기 때문이다. 여기서 분할정복과 차이가 생기는 부분은 원래의 문제를 부분 문제로 나누는 방식에 있다. 동적 계획법의 경우 주어진 문제를 나눌 때 부분 문제를 최대한 많이 이용하도록 나눈 다음, 주어진 부분 문제의 정답을 한 번만 계산하고 저장해둔 뒤 다시 한 번 이 부분 문제를 이용할 때에는 저장해둔 정답을 바로 산출하여 이용함으로써 속도를 향상시킨다.

 

위의 문제에 따르면,  N = 5인 경우 아래와 같다.

'5' * 1	5
'5' * 2	55, 10, 0, 25, 1

그리고 3은 5 와 55로 표현 가능하다.

'5' * 3

555, 60, -50, 275, 15, -5, 50, 0, 5, 30, -20, 125, 6, 4, 2

 즉, 가장 '5' * i는 '5'*x 와 '5'*(i-x)로 표현 가능하다.

 

이를 이용해서 문제를 풀어보았다.

def solution(N, number):
    answer = [set([int(str(N)*i)]) for i in range(1, 9)]
    
    # 예를 들어 N = 5, number = 5인 경우, 5 하나로 표현 가능하므로, return 1
    if N == number :
        return 1

	# N을 사용한 횟수의 최솟값이 8 이상이면 -1 return
    # answer[0]의 경우에는 {N} 한가지 경우밖에 없으므로 1부터 시작 & 인덱스는 0부터 시작하므로 8회가 answer[7]
    for i in range(1, 8) :
    	# answer[i]
        for j in range(i) :
            for y in answer[j]:
                for x in answer[i-j-1] :    
                        answer[i].add(y+x)
                        answer[i].add(y*x)
                        answer[i].add(y-x)
                        if y > 0 :
                            answer[i].add(x//y)
                if number in answer[i] :
                    return i+1

    return -1