[프로그래머스/파이썬] N으로 표현

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

프로그래머스

문제 유형 : dp를 베이스로 하는 완전 탐색

 

문제 풀이 : 숫자 n개를 이용해 만들기 위해선, 숫자 n-1개로 만든 수들을 이용해야 한다.

 

유의점 : N=4, number = 17 인 경우

-> 17 = (4*4) + (4/4)

 

이 경우는, 4를 4개를 이용해 17을 만들었는데, 4를 3개 이용한 조합에서 사칙연산한 것이 아니라,

4를 2개 이용한 숫자(= 4*4)와 4를 2개 이용한 숫자(= 4/4)를 이용해 답을 구한 것이다.

 

즉, 단순히 숫자 n개를 이용한 수를 만들기 위해선 n-1개로 만든 수에다가 추가로 사칙연산 하는 방법 이외에도

1개 + n-1개

2개 + n-2개

...

n-1개 + 1개

와 같은 다양한 조합들을 고려해야 한다.

def solution(N, number):
    answer = -1
    sign = 1
    breaker = False
    dp = [[] for _ in range(10)]
    
    # N 사용 횟수가 8보다 크면 -1 return
    for idx in range(1,9):
        dp[idx].append(int(str(N)*idx))
        
        if int(str(N)*idx) == number:
            answer=idx
            break
        
        if idx != 1:
            for i in range(1,idx):
                for num1 in dp[i]:
                    for num2 in dp[idx-i]:
                        dp[idx].append(num1+num2)
                        dp[idx].append(num1-num2)
                        dp[idx].append(num1*num2)
                        if num2 > 0:
                            dp[idx].append(num1//num2)
                    
                if number in dp[idx]:
                    answer = idx
                    breaker=True
                    break
                    
        if breaker: break
        
    return answer