[프로그래머스] Lv.3 n으로 표현

Python3, 동적프로그래밍

문제

제한사항

입출력 예시

나의 풀이 (시도)

주요 포인트

DP(동적 프로그래밍)을 사용해서 풀이

처음에 어떤 걸 사용해야 하는지 잘 보이지 않았음.

최종 코드

def solution(N, number):
    answer = 0
    # 중복 없애기 in보다 효율성 좋음
    dp = [set() for i in range(9)]
    
    # 1부터 8까지 돌기
    for i in range(1, 9):
        # N을 1부터 8개까지 만듬        
        dp[i].add(int(str(N) * i))
        
        for j in range(i // 2 + 1):
            for op1 in dp[j]:
                for op2 in dp[i-j]:
                    dp[i].add(op1 + op2)
                    dp[i].add(op1 - op2)
                    dp[i].add(op2 - op1)
                    dp[i].add(op1 * op2)
                    # 나눗셈 0으로 안 나누게 조심
                    if op2 != 0:
                        dp[i].add(op1 // op2)
                    if op1 != 0:
                        dp[i].add(op2 // op1)

        # 만약 필요한 결과값이 dp 안에 있으면 i(N을 쓴 개수) 출력
        if number in dp[i]:
            return i
        
    return -1

.
.
어렵네요 .. 발전하겠죠 ..