[프로그래머스] N으로 표현 (python 파이썬)

👉 N으로 표현

---

✍ 내 코드

---

# 3레벨     코딩테스트 고득점 Kit     N으로 표현
from collections import defaultdict


def solution(N, number):
    dic = defaultdict(set)
    dic[1] = set([N])
    dic[2] = set([10 * N + N, N // N, N + N, N * N, N - N])

    for i in range(1, 3):
        if number in dic[i]:
            return i

    count = 3
    while count:
        print(count)
        if count > 8:
            return -1

        dic[count].add(int(str(N) * count))
        for r in range(1, count // 2 + 1):
            for i in dic[r]:
                for j in dic[count - r]:
                    dic[count].add(i - j)
                    dic[count].add(j - i)
                    dic[count].add(i * j)
                    dic[count].add(i + j)
                    if j != 0:
                        dic[count].add(i // j)
                    if i != 0:
                        dic[count].add(j // i)
        if number in dic[count]:
            return count
        else:
            count += 1

---

✍ 팁

• 이전에 구한 값을 이용하여 풀면된다
• set을 이용하여 중복을 제거하면 연산량이 줄어든다

👉 잡담

뇌절을 크게하여 오래 걸린 문제였다ㅠㅠ
5를 구할려면 1집합+4집합 이런식으로 더해야하는데 3집합+4집합 이런식으로 N-2, N-1 집합으로 연산을 해서 시간초과가 계속 나왔었다ㅎㅎ..