문제 링크

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

문제 설명

• N이 주어질 때
• N으로 사칙연산, 괄호, 이어붙이기 만으로 number을 나타낼 수 있는 방법 중 N 사용 횟수 최솟값

(예시)
12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

풀이

• N을 사용하는 횟수로 DP
• N을 (1번 사용해서 만들 수 있는 수), (2번 사용해서 만들 수 있는 수), ... 저장
• 점화식
  • N을 j번 사용해 만들 수 있는 수
    • (x번 사용해서 만들 수 있는 수) + (j-x번 사용해서 만들 수 있는 수)

느낀 점

• 처음에 표현하려는 수를 이용해 DP를 하려고 했는데
• 목표로 하는 수를 수를 계산하는데 사용되는 부분이
• 이미 계산된 값이 아니어서 불가능했다
• 전에 풀었던 문제인데 여전히 어려워서 힌트를 봤다

코드

def solution(n, number):
    set_list = [set() for i in range(9)]
    for i in range(1, 9):
        set_list[i].add(int(str(n) * i))
    for i in range(9):
        for j in range(i):
            for x in set_list[j]:
                for y in set_list[i-j]:
                    set_list[i].add(x + y)
                    set_list[i].add(x - y)
                    set_list[i].add(x * y)
                    if y:
                        set_list[i].add(x // y)
    for i in range(9):
        for j in set_list[i]:
            if j == number:
                return i
    return -1