프로그래머스 고득점 kit #DP : N으로 표현

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

프로그래머스

 

 

아직도 DP가 조금 어렵다.

 

어떤 값을 기준으로 dp 를 만들어야할지,

dp가 1차원일지 2차원일지 판단하지 못한다.

 

아무래도, 모든 경우의 수를 수기로 써내려가며 점화식을 찾는 연습이 부족한 것 같다.

def solution(N, number):
    answer = -1
    # dp를 무엇으로 기준으로 잡냐에 따라서 문제를 풀 수 있고 없고가 갈린다.
    # 보통 dp에서는 범위가 작게 나온 것이 기준이 되는 경우가 많다.
    # "최솟값이 8보다 크면 -1을 return 합니다."라는 조건이 있다.
    # 즉, 숫자를 최대 8개까지만 사용가능하는 것이다.
    # 이게 이 문제의 핵심이다.
    dp = [set() for _ in range(9)] # 1~8 인덱스 사용

    for i in range(1, 9):
        tmp = int(str(N)*i)
        dp[i].add(tmp)
        for j in range(0, i):
            for item1 in dp[j]:
                for item2 in dp[i-j]:
                    added = item1+item2
                    dp[i].add(added)
                    minused = item1-item2
                    dp[i].add(minused)
                    multied = item1*item2
                    dp[i].add(multied)
                    if item2>0:
                        divided = item1//item2
                        dp[i].add(divided)
        if number in dp[i]:
            return i
    return answer

"""
연산 방법 정리 (5가지) : 덧셈, 뺄셈, 나눗셈, 곰셈, 숫자 붙여쓰기
ex : 5
1개 : 5
2개 : 5+5, 5-5, 5/5, 5*5, 55
3개 :
    (5+5)+5=15, (5+5)-5=5, (5+5)/5=2, (5+5)*5=50 | (5+5)5=105, 이런건 안되는 듯
    (5-5)+5=6, (5-5)-5=-4, (5-5)/5=1/5, (5-5)*5=5
    5/5+5, 5/5-5, 5/5/5, 5/5*5
    5*5+5, 5*5-5, 5*5/5, 5*5*5
    55+5, 55-5, 55/5, 55*5
-> 따라서 점화식은 dp[i]의 원소 = dp[i-j]의 원소 (사칙연산) dp[j]의 원소

"""
# dp가 어려우면 2차원으로 빠진다는 것을 명심하라.