[Level3] N으로 표현

1118 단어 DPprogrammersDP

🛠 문제

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


👩🏻‍💻 해결 방법

예를 들어 dp[3](= N을 3번 사용)은 N의 길이가 3인 경우(NNN), dp[0]과 dp[1]을 사용하는 경우로 생각할 수 있다
따라서 dp를 사용해 문제를 풀었고, dp에 저장하기에 앞서 set을 사용해 중복된 수는 저장되지 않게 했다
또한, 최솟값(N의 사용횟수)가 8 초과이면 -1을 return 해야했기에 for문 범위를 (1, 9)로 설정하였고, 처음부터 answer의 값에는 -1을 넣어주었다

소스 코드

def solution(N, number):
    answer = -1
    dp = []
    
    for i in range(1, 9):
        case = set()
        i_num = int(str(N)*i)
        case.add(i_num)
        
        for j in range(0, i-1):
            for op1 in dp[j]:
                for op2 in dp[-j-1]:
                    case.add(op1+op2)
                    case.add(op1*op2)
                    case.add(op1-op2)
                    if op2 != 0:
                        case.add(op1//op2)
        
        if number in case:
            answer = i
            break
        dp.append(case)
    return answer

좋은 웹페이지 즐겨찾기