Level 3 N으로 표현 Python 3

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

코딩테스트 연습 - N으로 표현

 

최종 풀이

• GitHub https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_N으로표현.py

hwayeon351/Programmers-Algorithms

def solution(N, number):
    if number == N: return 1
    dp = [0, [N]]
    for i in range(2, 9):
        p_set = set([int(str(N)*i)])
        for j in range(1, i//2+1):
            for x in dp[j]:
                for y in dp[i-j]:
                    p_set.add(x+y)
                    p_set.add(x-y)
                    p_set.add(y-x)
                    p_set.add(x*y)
                    if y!=0: p_set.add(x//y)
                    if x!=0: p_set.add(y//x)
        if number in p_set:
            return i
        dp.append(p_set)
    return -1

---

풀이 과정

i개의 N으로 표현할 수 있는 수의 집합들을 dp[i]에 저장하면서 bottom-up방식으로 풀어나가며 집합에 number가 있으면 return i를 해줘서 문제를 해결할 수 있었다.

동적프로그래밍 문제는 memoization할 대상을 선정하는 것과 memoization된 값을 활용하여 그 다음 값을 어떻게 찾아나갈지에 대한 규칙을 구하는 것이 핵심이면서 어려운 것 같다.

처음에 접근할 때, dp[i]에서 i는 숫자, dp[i]는 i를 표현하는데 필요한 N의 개수의 최솟값을 담아내서 풀려고 했는데 N이 값이 무엇이냐에 따라 초기에 dp[2] ~ dp[N-1]까지 설정하는데 어려움을 겪었다.

 

이후, dp[i]는 i개의 N을 사용하여 표현할 수 있는 수의 집합으로 바꾸어 생각하여 문제를 해결 할 수 있었다.

문제의 제한 사항을 살펴보면 애초에 이 경우 dp[8]까지만 구해서 그 안에 number를 표현할 수 있는지만 살펴보면 되는 것이기에 훨씬 간단하게 풀 수 있다.

#N으로 표현
def solution(N, number):
    #number와 N이 같은 경우 N 하나로 number 표현 가능하므로 return 1
    if number == N: return 1
    
    #dp의 idx는 N의 개수, dp[i] = N을 i개 사용해서 얻을 수 있는 숫자 집합
    #dp[1] = N, N 한 개로는 숫자 N만 표현 가능
    dp = [0, [N]]
    
    #N을 2~8개 사용하여 표현할 수 있는 숫자를 구하기
    for i in range(2, 9):
        #N을 i개 사용하여 구할 수 있는 숫자들을 담은 집합
        #i==2인 경우, NN을 만들 수 있으므로 p_set에 추가
        p_set = set([int(str(N)*i)])
        
        #dp 핵심 연산 Part
        #이전 dp값을 활용하여 i = j+k가 되는 dp[j], dp[k]의 수 집합을 활용하여 N을 i개 사용하여 만들 수 있는 수의 집합을 구한다.
        #j = i의 절반 이하 값 = 1 ~ i//2
        #k = i-j
        #i=5인 경우, (j,k) = [(1,4),(2,3)]
        for j in range(1, i//2+1):
            #j개로 표현할 수 있는 수 x와 k=i-j개로 표현할 수 있는 수를 연산하여 p_set에 추가
            for x in dp[j]:
                for y in dp[i-j]:
                    p_set.add(x+y)
                    p_set.add(x-y)
                    p_set.add(y-x)
                    p_set.add(x*y)
                    #피연산자가 0이 되지 않도록 예외처리
                    if y!=0: p_set.add(x//y)
                    if x!=0: p_set.add(y//x)
        #number가 p_set에 있다면 더이상 수의 집합을 만들지 않아도 되므로 return i
        #i in range(2, 9)이므로 현재 i개로 표현한 경우가 최솟값이다.
        if number in p_set:
            return i
        
        #number가 생성되지 않은 경우 dp[i]에 p_set을 저장한다.
        dp.append(p_set)
    #number을 8개의 N으로 표현할 수 없으므로 return -1
    return -1
#시간복잡도 = O(2^n), 공간복잡도 = O(2^n)