[Python] 동적계획법(DP)_N으로 표현(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 합니다.

입출력 예

입출력 예 설명

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

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

DP 기초문제 예제) 1로 만들기

x = int(input())
d = [0]*30001
for i in range(2, x+1):
	d[i] = d[i-1] + 1
    
    if i % 2 == 0:
    d[i] = min(d[i], d[i // 2] + 1)
    if i % 3 == 0:
    d[i] = min(d[i], d[i // 3] + 1)
    if i % 5 == 0:
    d[i] = min(d[i], d[i // 5] + 1)

print(d[x])

문제풀이

N이라는 숫자를 활용해서 Number을 만드는 것 (최소의 개수 사용한 결과 return)

1) DP 문제라는 것은 이전에 실행의 결과 값이 다음 실행에 영향을 주는 것으로 인식해서 이전 값들의 조합을 살펴보게 된다.

• N이 i 개 만큼 있는 set을 만들어 준다.
• dp[1] 일 경우, {5} , dp[2] 일 경우 {5+5, 5-5, 5//5, 5*5}이기 때문에 이전(dp[1])의 구성요소의 사칙 연산 결과로 구성 되어있다.
• 이처럼 dp[3]을 해보면, 555 , (dp[1] 연산 dp[2]) , (dp[2] 연산 dp[1])이 되는것을 볼 수 있다.
• 만들어진 dp[i] set 에서 number이 존재하면 i를 반환.
• 끝까지 발견 못하면 -1을 출력

2) 1번 사용해서 만들 수 있는 수들, 2번 사용해서 만들 수 있는 수들, 3번 사용해서 만들 수 있는 수들.........을 찾아나가다가, 그 수들 중에 number이 포함되면 멈추고 리턴하면 된다.

dp 원리는
3번 사용해서 만들 수 있는 수들 =
1번 사용해서 만들 수 있는 수들 [사칙연산] 2번 사용해서 만들 수 있는 수들 +
2번 사용해서 만들 수 있는 수들 [사칙연산] 1번 사용해서 만들 수 있는 수들

이런식으로 dp 배열을 꾸려 나가면 된다.

def solution(N, number):
    answer = -1
    dp = []
    
    for i in range (1,9) : 
    # i = N의 개수
    	all_case = set()
        check_number = int(str(N)* i)
        # {N}, {NN} , {NNN}...
        all_case.add(check_number)
        
        for j in range(0,i-1):
        //j 개를 사용해서 만든 값들
            for op1 in dp[j]:
                for op2 in dp[-j-1] :
                    all_case.add(op1 - op2)
                    all_case.add(op1 + op2)
                    all_case.add(op1 * op2)
                    if op2 != 0:
                        all_case.add(op1 // op2)
                        
        if number in all_case:
            answer = i
            break
            
        dp.append(all_case) 
    return answe

def solution(N, number):
    possible_set = [0,[N]] # 조합으로 나올수 있는 가능한 숫자들, 여기에 계속 append하며 이후에 사용함
    if N == number: #주어진 숫자와 사용해야 하는 숫자가 같은 경우는 1개면 족하므로 1으로 놓는다. 
        return 1
    
    for i in range(2, 9): # 2부터 8까지로 횟수를 늘려 간다. 
        case_set = [] # 임시로 사용할 케이스 셋, 각 I 별로 셋을 만들어 possible set에 붙인다.
        basic_num = int(str(N)*i) # 같은 숫자 반복되는 거 하나를 추가한다.
        case_set.append(basic_num)
        
        for i_half in range(1, i//2+1): # 사용되는 숫자의 횟수를 구해야 하는데, 절반 이상으로 넘어가면 같은 결과만 나올 뿐이므로 절반까지만을 사용한다. 
            for x in possible_set[i_half]:
                for y in possible_set[i-i_half]: # x와 y를 더하면 i 가 되도록 만든 수다. 
                    print(possible_set)
                    case_set.append(x+y)# 각 사칙연산 결과를 더한다.
                    case_set.append(x-y)
                    case_set.append(y-x)
                    case_set.append(x*y)
                    if y !=0:
                        case_set.append(x/y)
                    if x !=0:
                        case_set.append(y/x)
            
            if number in case_set:
                return i
            possible_set.append(case_set) # 최종 결과물 set에 사칙 연산 결과를 더한다.
    return -1 #N 이 8까지 답이 없으면 -1을 출력한다.

3)

def solution(N, number):
    dp = [set() for i in range(9)] # 사용횟수에 따라 가능한 숫자를 담을 리스트
    
    for i in range(1, 9): # 1~8
        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

• 연산 횟수에 따른 가능한 숫자를 담을 리스트 dp를 만들었다. 각 경우의 수는 set을 이용해서 중복없이 담았다. set을 사용한 이유는 중복뿐만 아니라 in 탐색에 있어서도 효율이 높기 때문이다.

• 경우의 수는 먼저 횟수만큼 숫자가 이어 붙여진 값을 담는다. 그리고 다른 경우의 수는 많은 연산을 필요로한다. 예를 들어 5의 경우, 1번의 연산으로 만들어진 숫자들(first)과 4번의 연산으로 만들어진 숫자들(second) 을 사칙연산한 숫자들로 구성된다. 즉 합으로 5를 만들 수 있는 자연수인 (1,4) (2,3) 을 모두 사칙연산해야한다.

• 이 때 나눗셈에 유의하여야한다. 나누기는 순서가 바뀌면 답이 달라질 뿐만아니라 0으로 나누면 오류와 함께 종료될 수 있다.

• 하나의 작업이 끝날때마다 number가 있는지 확인하고 있다면 i (연산횟수)를 반환한다.

• 다행히 연산이 8보다 커지면 멈추고 -1을 출력하기 때문에 4중 for문이 무사히 돌아간다.