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

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

코딩테스트 연습 - N으로 표현

# 프로그래머스 N으로 표현 실패

def solution(N, number):
    answer = 0
    dp = [10000]*(1000000)
    for i in range(1, 7):
        s = str(N)*i
        dp[int(s)] = i
    for i in range(2, 100000):
        if i > N:
            dp[i] = min(dp[i], dp[i*N]+1, dp[i+N] + 1, dp[i-N]+1,)
        else:
            dp[i] = min(dp[i], dp[i*N]+1, dp[i+N]+1)
    answer = dp[number]
    if answer >= 8:
        answer = -1
    return answer

 

 

이 문제를 2부터1000000까지의 수를 하나씩 경우를 다 따져가면서 dp를 구성하면 될거라고 접근했다. --> 접근법이 잘못되었다.

 

def solution(N, number):
    answer = -1
    dp = []
    
    for i in range (1,9) : 
    	all_case = set()
        check_number = int(str(N)* i)
        all_case.add(check_number)
        
        for j in range(0,i-1):
            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 answer

결국 다른분의 풀이를 참고하여 해결하였다. dp[i]는 [i]개로 만들 수 있는 수들의 조합이 들어간다. 

i번째 dp값은 dp[j]과 dp[i-j-i] 값을 조합한 값 이므로, 위의 for문을 돌면서 문제를 해결 할 수 있다.