[프로그래머스 42895 파이썬] N으로 표현 (level 3, DP)

알고리즘 유형 : DP(Dynamic Programming)
풀이 참고 없이 스스로 풀었나요? : X

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

소스 코드(파이썬)

import sys
from itertools import product
input = sys.stdin.readline

def solution(N, number):
    answer = 1
    
    # DP[k] : N을 k번 써서 나타낼 수 있는 수의 집합
    DP = [set() for _ in range(9)]
    DP[1].add(N)
    
    if N == number:
        return answer
    
    # N을 cal_cnt번 써서 만들 수 있는 수를 구해서 DP에 저장
    # 그 과정에서 number와 같은 수를 만들 수 있다면 바로 answer 리턴
    for cal_cnt in range(2, 9):
        answer += 1
        # N을 cal_cnt번 이어붙여 만든 수
        DP[cal_cnt].add(int(str(N)*cal_cnt))
        
        # DP[N] = DP[i] (사칙연산) DP[N-i] (1 <= i <= N-1)
        for i in range(1, cal_cnt):
            j = cal_cnt - i
            
            # 데카르트 곱
            for x, y in product(DP[i], DP[j]):
                DP[cal_cnt].update({x+y, x-y, x*y})
                
                if y != 0:
                    DP[cal_cnt].add(x//y)
            
            if number in DP[cal_cnt]:
                return answer
        
    return -1

풀이 요약

1. 문제의 핵심 아이디어는 다음과 같다.

   N을 1번 써서 만들 수 있는 수를 먼저 구한다. 이걸 cnt[1]이라고 해보자.

   cnt[2]는 cnt[1]을 활용하여 구할 수 있음이 직관적으로 보인다.

   cnt[3]은 cnt[1], cnt[2]를 활용하여 구할 수 있을 것 같다.

2. cnt[7]의 경우를 생각해보자.

   1) 괄호로 묶이는 경우를 고려하기 위해 두 쌍의 집합을 사칙연산하여 cnt[7]를 모두 구한다. cnt[1], cnt[6] / cnt[2], cnt[5] 등등

   2) 이 때, cnt[1], cnt[6]부터 cnt[2], cnt[5] ... cnt[6], cnt[1]까지, 자리가 서로 뒤바뀌는 경우도 구해줘야한다. 뺄셈과 나눗셈의 경우, 위치에 따라 값이 달라지기 때문이다. 이 때 덧셈과 곱셈의 경우에는 값이 그대로인데 이를 위해 cnt를 set으로 선언해주자.

   3) 주의할 점은, 사칙연산의 결과가 음수여도 유효한 값이다. 음수를 사칙연산하여 만들 수 있는 또 다른 양수들이 있을 것이기 때문이다.

3. DP의 로직으로 푼 풀이다. 정리하면, 점화식은 DP[k] = DPi DP[N-i] (1 <= i <= N-1)

   이 것을 바텀업으로 푼 것이다.

배운 점, 어려웠던 점

• 바텀업 규칙은 생각했는데 점화식을 DP[N] = DPN-1 DP[1] 이렇게 생각해버려서 틀렸다. 고려해야 할 케이스들을 많이 놓친 것 같다. 점화식을 세울 때, 문제의 모든 조건에 부합하는 점화식인지 꼼꼼하게 고려해야겠다.