동적계획법(Dynamic Programming) 대표 문제 풀이 - N으로 표현

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42895

프로그래머스

---

동적 계획법(Dynamic Programming)

주어진 최적화 문제를
재귀적인 방식으로 보다 작은 부분 문제로 나누어
부분 문제를 풀어, 이 해를 조합하여 전체 문제의 답에 이르는 방식

• 알고리즘의 진행에 따라 탐색해야 할 범위를 동적으로 결정함으로써 탐색 범위를 한정할 수 있음
• Knapsack Problem : 참고 싸이트 https://gsmesie692.tistory.com/113

Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem)

 

문제 해결

• N을 한번 사용해서 만들 수 있는 수들 -> N을 두번 사용해서 만들 수 있는 수들  -> N을 세번 사용해서 만들 수 있는 수들  -> 하다가 나오는 수를 리턴
• 만약 8번까지 안나오면 -1

def solution(N, number):
    if N == number: # 1개 가지고 만들수 있는 경우는 따로 체크해 줘야함
        return 1
    s = [set() for _ in range(8)]  # n을 1번 부터 8번까지 사용해 만들수 있는 경우의 수
    for i, x in enumerate(s, start=1):
        x.add(int(str(N) * i))
    for i in range(1, len(s)):
        for j in range(i):
            for op1 in s[j]:
                for op2 in s[i - j - 1]:
                    s[i].add(op1 + op2)
                    s[i].add(op1 - op2)
                    s[i].add(op1 * op2)
                    if op2 != 0:
                        s[i].add(op1 // op2)
        if number in s[i]:
            answer = i + 1
            break
    else:
        answer = -1

    return answer