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

문제

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

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

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

 

 

 

 

내 생각

주어진 숫자 N으로 사칙연산(+, -, *, /)만을 이용하여 number를 만들 수 있는데, 그 때 사용하는 N의 최소 횟수를 찾는 문제이다!

1. 연산 횟수에 따른 가능한 숫자를 담을 리스트 dp를 만들고 set으로 중복없이 담기!
 여기서는 중복없이 담는게 포인트인거 같다.

2. 그리고 경우의 수를 dp 배열에 저장하는데 단순히 숫자를 이어 붙여진 값을 저장한다. : N * i 수

3. 사칙연산을 하면서 number이 있는지 확인하기!

 

움 예시로 보면 더 편하다.

 

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

 

이걸 활용해보면,

1. 전체적으로 볼 때 dp 배열에는 5, 55, 555 ... 가 있는 것이다.

2. dp 과정

2-1. 숫자 5를 1번 이용 : 5

2-2. 숫자 5를 2번 이용 : 5+5 , 5-5, 5*5, 5/5 : 12는 존재하지 않는다.

2-3. 숫자 5를 3번 이용 : 5+55, 5-55, 5*55, 5/55, 5+(5+5), 5-(5+5), ...

이런식으로 계산되어져 가는 것이다!

그러니까 number을 만들 수 있는 조합을 N을 사용하여 사칙연산을 쭉 하는 것이다. 

 

 

 

 

내 코드

def solution(N, number):
    # DP 배열 초기화
    dp = [set() for _ in range(9)]

    # 모든 경우의 수 저장
    for i in range(1, 9):
        dp[i].add(int(str(N) * i))

    # dp
    for i in range(1, 9):
        for j in range(1, i):
            for x in dp[j]:
                for y in dp[i - j]:
                    dp[i].add(x + y)
                    dp[i].add(x - y)
                    dp[i].add(x * y)
                    if y != 0:
                        dp[i].add(x // y)

        # 목표 숫자에 도달하면 결과 반환
        if number in dp[i]:
            return i
    return -1