[파이썬] 프로그래머스 커뮤러닝 2주차 N으로 표현

 

 

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

프로그래머스

 

동적계획법

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

 

어디 까지 하고 이를 다시 탐색하는 방법으로 탐색 범위를 한정 할 수 있다.

피보나치 수열을 동적계획법에 적용

 

동적계획법을 사용하면, 문제를 부분으로 쪼개서 이를 해결한다. 앞의 문제를 풀고 이를 사용하여 다음문제에 활용한다.

 

 

대표적인 문제는 Knapsack Problem임

 

 

풀이 아이디어

N = 5 일 때, 경우의 수를 +-x/모두 계산하여 이를 집합으로 구성하여 가짓 수를 만들어서 

덧셈과 곱셈이 앞뒤가 바뀌어도 빠지는 것이 있어도 전체 갯수가 많아 지긴 하지만 5의 경우는 19가지 정도 생성됨

 

 

주의 할 것은, 괄호를 사용이 가능할 때, 괄호를 치고 연산을 한것과 이것은 동일한것으로 봐도 된다. 

 

 

 

 

문제 구현

def solution(N, number):
    s = [set() for x in range(8)]
    for i, x in enumerate(s, start=1):
        x.add(int(str(N) * i)) # 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