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

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42895?language=python3

💻 문제 풀이 : Python

def get_Ns(N, idx):
    # NN(idx==1), NNN(idx==2), NNNN(idx==3)...과 같은 형태 만드는 함수
    result = N
    for i in range(1, idx + 1):
        result = result * 10 + N
    return result

def solution(N, number):
    if N == number:
        return 1  # N과 number가 같다면, N을 한 번 사용해서 number를 만들 수 있음

    DP = [set() for _ in range(8)]
    # DP에 저장할 것 -> DP[i] : i개의 N으로 만들 수 있는 숫자들 (set)

    DP[0].add(N)  # 한 개의 N으로 만들 수 있는 수는 N뿐임

    for k in range(1, 8):
        # DP[k]에 NNN...(k+1만큼 반복)과 같은 형태 삽입
        DP[k].add(get_Ns(N, k))

        # DP[k]에 사칙 연산의 결과또한 삽입
        for i in range(k):
            for j in range(k):
                if i + j + 1 != k:
                    continue
                # i+j+1 == k 일때
                for a in DP[i]:
                    for b in DP[j]:
                        DP[k].add(a + b)
                        # 검사가 필요한 연산들

                        # (1) 음수 존재하면 안됨
                        if a - b > 0:
                            DP[k].add(a - b)

                        DP[k].add(a * b)

                        # (2) 0 존재하면 안됨
                        if a // b > 0:
                            DP[k].add(a // b)

        if number in DP[k]:  # DP set에 number에 해당하는 값이 있으면 k+1을 반환
            return k + 1
    return -1

출처 : https://velog.io/@euneun/프로그래머스-N으로-표현-DP-동적계획법-C

---

📌 memo

DP 풀이 방법

1. 점화식 세우기
   DP 배열안에 무엇을 넣을지 고민해보기

# DP[i]: i 개의 N으로 만들 수 있는 수의 조합들 넣기

2. 점화식을 어떻게 채워야 효율적일지 고민해보기
   위 풀이에서는 unordered_map을 통해 빠르게 검색하도록 최적화