211216 - N으로 표현

◾ N으로 표현 : 프로그래머스 LEVEL 3

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

문제

아래와 같이 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은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.

출력

• N 사용횟수의 최소값
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

N	number	return
5	12	4
2	11	3

---

◾ 풀이

1. 해설

• 각 횟수별로 만들 수 있는 수를 찾으며 해결할 수 있다.
• 사용 횟수 I인 경우 만들수 있는 수는 아래와같다.
  • (NN...N) 1개 : 길이 I
  • i 횟수인 수와 j 횟수인 수의 사칙 연산 결과(단, i + j == I)
• 횟수가 1인 경우부터 8인 경우까지 반복하며 number가 존재하는 횟수를 찾는다.
• 존재하지 않는다면 그 이상의 횟수인 것으로 -1을 반환한다.

---

2. 프로그램

1. dp 선언
2. 횟수가 1인 경우 추가
3. 횟수가 2 ~ 8인 경우 추가
   • 사용 횟수 I인 경우
   • (NN...N) 1개 : 길이 I
   • i 횟수인 수와 j 횟수인 수의 사칙 연산 결과(단, i + j == I)
4. 각 횟수를 진행하며 number가 존재하는지 확인
   • 존재한다면 해당 횟수 반환
   • 존재하지 않으면 다음 횟수 진행
5. 가능한 횟수가 없다면 -1 반환

# 코드
def solution(N, number):
    answer = -1
    dp = {i : set() for i in range(1, 9)}
    
    if N == number:
        answer = 1
        return answer

    dp[1].add(N)
    for i in range(2, 9):
        dp[i].add(int(str(N)*i))
        for half in range(1, i//2+1):
            for x in dp[half]:
                for y in dp[i-half]:
                    add, minus1, minus2, mul = x+y, x-y, y-x, x*y
                    if 0 < add <= 32000 :
                        dp[i].add(add)
                    if 0 < minus1 <= 32000:    
                        dp[i].add(minus1)
                    if 0 < minus2 <= 32000:
                        dp[i].add(minus2)
                    if 0 < mul <= 32000:
                        dp[i].add(mul)
                        
                    if y != 0:
                        quotient, mod = divmod(x, y)
                        if mod == 0 and 0 < quotient <= 32000:
                            dp[i].add(quotient)
                    if x != 0:
                        quotient, mod = divmod(y, x)
                        if mod == 0 and 0 < quotient <= 32000:
                            dp[i].add(quotient)
        if number in dp[i]:
            answer = i
            return answer

    return answer