(프로그래머스 Lv.3) N으로 표현 / with.DP

문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42895

코드

def solution(N, number):
    dp = [set() for _ in range(9)]

    # i개의 N으로 만들 수 있는 초기값
    for i in range(1, 9):
        dp[i].add(int(str(N) * i))
    
    # 1부터 8까지의 사용 횟수에 대해 탐색
    for i in range(1, 9):
        for j in range(1, i):
            for op1 in dp[j]: 
                for op2 in dp[i - j]:
                    dp[i].add(op1 + op2)
                    dp[i].add(op1 - op2)
                    dp[i].add(op1 * op2)
                    if op2 != 0:
                        dp[i].add(op1 // op2)
        
        if number in dp[i]:
            return i
    
    return -1

풀이

1. 숫자 N을 최소한으로 사용해서(8번 이하) number를 만들어야함.
2. 그렇다면 숫자 N을 집합으로 만들어서, 횟수별로 만들 수 있는 조합을 계산하고, 그 조합 안에 number가 있다면 해당 횟수를 return하면 되지 않을까?
   • 왜 집합으로 생성해야되냐? => 사칙연산한 결과값이 중복되는 경우가 존재할 수 있기 때문. 따라서 중복되는 값은 제거하고, 탐색은 빠르게하기 위해서.
3. N을 i번 사용해서 만들 수 있는 숫자를 계산할 때 값을 j와 i-j로 쪼개서 작은 문제부터 해결한다. 이 때 for op1 in dp[j] 와 같이 for … in 문을 사용했기에 dp[j]에 있는 모든 요소를 순회하여 그 조합을 구한다. (e.g. N이 5일 때)
   • dp[1]
     • j=0, i-j=0 (5)
   • dp[2]
     • j=1, i-j=1 (5+5, 5-5, 5*5, 5//5, 55)
       • 이 때 55는 앞에서 dp[i].add(int(str(N) * i)) 으로 설정해준 초기값.
   • dp[3]
     • j=1, i-j=2 (5+5+5, 5-5-5, 5*5*5, 5//5//5, 5+55, 5-55, 5*55, 5//55, 555)
       • 근데 5-55의 값은 -50인데, number는 양수값으로만 주어지니 뺄셈 연산한 값이 양수일때만 dp에 저장하는게 낫지 않을까?
         • ㅇㅇ. 그렇게 해도 답 낼 때 상관은 없음. 심지어 그렇게 조건을 추가하는게 연산이 더 빠를 것. 근데, 음수값이 있다고해서 문제가 되는 것은 아님. 왜냐면 다음번 연산에서 그 값이 양수값으로 바뀔 수가 있기 때문.
     • j=2, i-j=1 …
4. 그러다 number가 이 안에 있으면 해당 횟수를 반환.