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

류성훈·2022년 7월 4일
0

코딩테스트

목록 보기
26/29

https://programmers.co.kr/learn/courses/30/lessons/42895?language=python3

다이나믹 프로그래밍을 이용하는 줄 몰랐으면 어려웠을 것 같은 문제

def solution(N, number):
    answer = 0

    dp = [set() for i in range(9)]
    
    for i in range(1,9):
        dp[i].add(int(str(N)*i))
        
        for j in range(i//2+1):
            for first in dp[j]:
                for second in dp[i-j]:
                    dp[i].add(first + second)
                    dp[i].add(abs(first-second))
                    dp[i].add(first*second)
                    if second != 0:
                        dp[i].add(first // second)
                    if first != 0:
                        dp[i].add(second // first)
                        
        if number in dp[i]:
            return i
    return -1

코드 설명

  • 중복값을 처리하기에 용이한 집합(set)으로 저장공간을 만들어 준다.
  • dp[i]에 들어갈 수 있는 값들을 add 해준다.
    - i 가 4라면, dp[i]는 5555, {dp[1],dp[4]}와의 연산, {dp[2],dp[3]}과의 연산이 필요하다. 이를 for문을 이용하여 구현한다.
  • for문을 돌리면서, 찾고싶은 숫자인 number가 있으면 index를 return 한다.
  • 없으면 마지막에 -1을 리턴한다.
profile
(전)Backend Developer / (현)Data Engineer

0개의 댓글