[프로그래머스] N으로 표현

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

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

Dynamic programming을 사용하는 문제로 분류 되어 있는데 완전히 점화식 같은 것을 세워 푸는 문제는 아닌 것 같습니다. 

 

우선 문제부터 간단히 요약해보면,

사칙연산으로 특정 수를 하나의 숫자로 만들어야 하는데 이 때 걸리는 최소 횟수를 return하여야 합니다. 

12를 5로 나타내는 방법들입니다. 이중에서 가장 적게 5를 사용하는 경우 4번 사용해서 12를 구성할 수 있습니다. 따라서 이 때는 4를 return 해야 합니다. 

 

즉 solution(N, number)에서 

N : 1~9까지의 정수

number : 만들어야 하는 수

가 주어질 때, N을 이용해 number를 사칙연산해 만들 수 있는 최소 횟수를 return 해야 합니다. 

 

<Solution> 

직접 경우를 찾는 방법으로 하였는데 간단하게 설명해 보면, 

dp = [[N],[N+N, N-N, N*N, N//N, 10*N+N]]

다음과 같이 dp라는 list안에 1개로 만들수 있는 경우, 2개로 만들 수 있는 경우 등등 각각 N를 index+1 번 사용하여 만들 수 있는 숫자들이 들어가게 구성하였습니다. 

 

이후에 만약 6개로 구성된 경우를 조사하여야 한다면, 

(1,5), (2,4), (3,3), (4,2), (5,1) 에 대해 조사해서 만들 수 있게 하였습니다. 물론 이러한 과정중 중복을 제거하는 과정은 항상 존재합니다. 

 

더불어서 주의 해야하는 점은

1. 나누는 수가 0이 되는 경우(분모가0 -> zero division error)  -> (try except 문으로 처리) 2. (4+4)4 를 84로 생각 할 수 없다. 즉 숫자 여러개를 붙일 수 있는 경우는 그 숫자로만 구성이 되어 있는 경우이다. -> 항상 이러한 숫자를 list의 가장 끝에 두고, 따로 처리를 해주었다.

이 점에만 주의 해서 코드를 작성하면 된다. 2번째의 경우 처음 작성 할 때 잡지 못해서 일부 테스트 케이스에서 불통과가 나옴을 볼 수 있었다. 

def solution(N, number):
    dp = [[N],[N+N, N-N, N*N, N//N, 10*N+N]]
    # check if dp has value 
    if number in dp[0]:
        return 1
    elif number in dp[1]:
        return 2
    for i in range(3,9):
        # each step -> number of N 
        new_dp = []
        for j in range(1,i):
            for p in dp[j-1]:
                for q in dp[i-j-1]:
                    new_dp.append(p+q)
                    new_dp.append(p-q)
                    new_dp.append(p*q)
                    try:
                        tmp = p//q
                        new_dp.append(tmp)
                    except:
                        pass
                    new_dp.append(10**len(str(q))*p+q)
        new_dp = list(set(new_dp))
        if number in new_dp:
            return i
        dp.append(new_dp)
    return -1