프로그래머스(programmers) N으로 표현 python 정답[동적계획법 풀이]

프로그래머스(programmers) N으로 표현 python 정답[동적계획법 풀이]

문제 링크

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

프로그래머스

문제 정답

def solution(N, number):
    # 0도 포함 주의
    # 사용횟수에 따라 가능한 숫자를 담을 리스트
    dp = [set() for i in range(9)] 
    for i in range(1, 9): # 1~8
        dp[i].add(int(str(N)*i)) # 단순히 이어붙인 숫자
        # 0부터 i의 반까지. i가 6이라 치면 0 1 2 3 
        for j in range(i//2 + 1):
            # i개 사용
            for first in dp[j]:
                # (i - j)개 사용. i-j + j는 총 i개
                for second in dp[i-j]:              
                    dp[i].add(first + second)
                    dp[i].add(first - second)
                    dp[i].add(second - first)
                    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

문제 해설

(0,1), (0,1,2), (0,1,2,3)과 같이 i가 증가할 때마다 이전에 계산해둔 n을 j번 (0 ~ 최대 i //2까지) 사용한 결과를 이용해 새로운 결과를 만든다.

사실 숫자를 단순히 이어붙이는 부분까지는 이해하기 쉬운데,

아래에 이중 for문 (j와 first)쓰는 부분이 까다롭다.

두 가지 관점에서 파악하면 간단할 수 있다.

• 짝수건 홀수건 중간 인덱스 까지는 i //2 + 1로 구한다
  • 6일경우 3 + (6-3)까지 계산되어 정상
  • 5일 경우 3 + (5-3)까지 계산되어 정상
• j는 0부터 시작하여 0 + i 케이스 또한 포함해야 한다 (이어붙이기만 포함)