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

---

문제 분석

필요 개념

동적계획법(Dynamic Programming)

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

• 알고리즘의 진행에 따라
  탐색해야 할 범위를 동적으로 결정 함으로써
  탐색 범위를 한정할 수 있음

동적계획법(Dynamic Programming)의 적용 예

• 피보나치 수열 -> 재귀함수로 구현한다면?

f(4) =	f(3)		        +f(2)
	 =	f(2)		+ f(1) + f(1) + f(0)
	 =	f(1) + f(0) + f(1) + f(1) + f(0)

복잡도 : 지수함수의 형태

• 피보나치 수열 -> 동적계획법으로 구현한다면?

f(0) = 0,     f(1) = 1
f(2) = f(1) + f(0) = 1
f(3) = f(2) + f(1) = 1
f(4) = f(3) + f(2) = 1

복잡도 : 선형함수의 형태

---

Python 언어를 이용한 풀이

문제의 해결

동적계획법으로 설계

예제 (n = 5)

일반화(N = x)

결론

• 문제의 성질에 따라,
  동적계획법으로 풀어냄으로써
  탐색해야 하는 범위를 효과적으로 줄일 수 있음

코드

def solution(N, number):
    if N == number:
        return 1
    s = [set() for x in range(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

---