[프로그래머스 문제풀이] N으로 표현

DP문제는 아무래도 재귀 형식으로 표현하여 sub 문제들을 해결하여 큰 문제를 해결할 수있도록 하는 틀을 짜는 능력이 중요한것 같다.

이 문제의 경우에는 생각해보았지만, 해당 틀을 떠올리지 못해서 다른 소스코드를 참고하여 짠 코드이다.

발상 방법이야 여러개 있지만 내가 동작 시킨 코드는 아래와 같다.

def calc(A, B):
    ret = set()
    for a in A:
        for b in B:
            ret.add(a + b)
            ret.add(a - b)
            ret.add(a * b)
            if b != 0:
                ret.add(a // b)
    return list(ret)


def solution(N, number):
    answer = 0
    # merge plus substract times divide
    result = dict()
    for i in range(1, 9):
        result[i] = set()
        result[i].add(int(str(N) * i))
    #print(result)
    if N==number:
        return 1
    for i in range(2, 9):
        for j in range(1, i):
            k = calc(result[j], result[i-j])
            result[i].update(k)
        if number in result[i]:
            return i
    return -1
    return answer

각 자릿수별로 만들 수 있는 값을 int, set()으로 묶어 딕셔너리로 구현하고,

f(n) = {f(1):f(n-1) ... f(n-1):f(1)} (여기서 : 는 +-*//의 4가지 연산을 대입)

으로 설정하여 각 조합에 따라 각 연산을 set에 대입하여 문제를 풀 수 있도록 한다.

값의 계산은 8까지 하며, 8자리까지 수행하였을 때 원하는 값이 없다면(루프를 탈출한다면) 자동으로 -1을 리턴하도록 프로그램을 수행하였다.