Python : N으로 표현 DP

문제

풀이

• N의 수를 통해 나타낼 수 있는 모든 값을 구하고 그 사이에 원하는 답(number)가 있을 경우 리턴해준다.

잡담

• 풀다가 포기했다.
• 문제는 이해하겠는데 4중 for문 구현하는게 아직도 잘 이해가 안된다.
• 레벨 3은 아직 어려운 것 같다

전체코드

def solution(N, number):
    answer = -1
    # N개의 수로 표현 가능한 값을 담을 DP
    dp = []

    for i in range(1, 9):
        numbers = set()
        # 단순 반복되는 수를 담을 값 5, 55, 555,...
        numbers.add(int(str(N) * i))

        print("───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────")
        print(f'i-1: {i - 1}')
        print(f'dp : ', dp)

        # 0부터 답을 찾을 때(i-1) 까지, 최대 8번째 까지 모든 경우를 검색해본다.
        for j in range(0, i - 1):
            print("dp[j] : ", dp[j])
            # set(N이 j개 쓰일 때) 나올 수 있는 값 계산
            # j=0 1개 ,j=1 2개 ...
            # 경우의 수 구하기
            for x in dp[j]:
                for y in dp[-j - 1]:
                    print(f'j:{j} x:{x} y:{y}')
                    numbers.add(x + y)
                    numbers.add(x - y)
                    numbers.add(x * y)

                    if y != 0:
                        numbers.add(x // y)

        # 발견하면 리턴
        if number in numbers:
            answer = i
            break

        dp.append(numbers)

    return answer


print(solution(5, 12))