[프로그래머스] N으로 표현

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

DP문제인데 풀지 못했다. GPT 선생님께 여쭤보았다.

def solution(N, number):
    if N == number:
        return 1
    
    dp = [set() for _ in range(9)]
    dp[1].add(N)
    
    for i in range(2, 9):
        dp[i].add(int(str(N) * i))
        
        for j in range(1, i):
            for x in dp[j]:
                for y in dp[i - j]:
                    dp[i].add(x + y)
                    dp[i].add(x - y)
                    dp[i].add(y - x)
                    dp[i].add(x * y)
                    if y != 0:
                        dp[i].add(x // y)
                    if x != 0:
                        dp[i].add(y // x)
        
        if number in dp[i]:
            return i
    
    return -1

dp라는 집합 배열을 만드는데 이 집합 배열에는 N을 i번 사용해서 표현가능한 숫자를 저장한다.

그리고 1에는 이제 N을 저장해주고, n, nn, nnn인 경우를 각 집합에 넣어주면서 해당 숫자보다 작은 숫자와의 연산을 통해서 연산을 실행하여서 경우를 만들어줬고 그렇게 만들어진 숫자가 있으면 해당 index를 반환함으로써 종료했다.

제일 첫 번째 조건은 굳이 있어야할까 싶어서 빼봤는데 마지막 테스트케이스가 통과가 되지 않아서 냅뒀다. 지피티 선생님은 가장 간단한 경우에 대해서 연산 굳이 안 시킬려고 넣어놨다고 했다.
나중에 다시 풀어볼 문제다.