[level 3] N으로 표현

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

프로그래머스

핵심포인트

✅ numbers라는 set()를 먼저 정의한다. DP[j]의 x와 DP[-j-1]의 y를 사칙연산해서 numbers에 add시켜준다. 이때 해당하는 값이 있으면 answer=i로 세팅한후에 return answer해준다.

#풀이1
def solution(N, number):
    answer = -1
    DP = []

    for i in range(1, 9):
        numbers = set()
        numbers.add( int(str(N) * i) )
        
        for j in range(0, i-1):
            for x in DP[j]:
                for y in DP[-j-1]:
                    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

if __name__ == '__main__':
    N = 5
    number = 12
    result = solution(N, number)
    print(result)

#풀이2
from collections import defaultdict

def solution(N, number):
	# dp[i]: N을 i번 사용해서 만들 수 있는 수들의 집합
    dp = defaultdict(set)

    for i in range(1, 9):
        dp[i].add(int(str(N) * i))  # NNN...N
        for j in range(1, i):
            for n1 in dp[j]:
                for n2 in dp[i - j]:
                    dp[i].add(n1 + n2)
                    dp[i].add(n1 - n2)
                    dp[i].add(n1 * n2)
                    if n2 != 0: dp[i].add(n1 // n2)  # 0으로 나눌 수 없음

        if number in dp[i]: return i # N을 i번 사용해서 number를 만들 수 있음

    return -1 # 최솟값이 8번보다 클 경우

[ CHAT-GPT 답변 ]