[프로그래머스][LV.3] N으로 표현 | python3

문제링크:  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은 1 이상 9 이하입니다.
- number는 1 이상 32,000 이하입니다.
- 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
- 최솟값이 8보다 크면 -1을 return 합니다.

---

 

문제풀이

1. 1번 사용할 때는 N

2. 2번 사용할 때는 ex) N=5, 5+5, 5*5,5-5,5/5 가 되므로 

    => 1번 (op) 1번 

3. 3번 사용 할 때는 1번 (op) 2번, 2번 (op) 1번 

4. 4번 사용 할 때는 1번 (op) 3번, 2번 (op) 2번, 3번 (op) 1번

.

.

N. N번 사용할 때는 1 (op) N-1, 2 (op) N-2, 3 (op) N-3,... N-1 (op) 1 까지 계산

 

5,55,555는 계산 없이 들어가기 때문에 처음부터 저장해줌.

 

질문하기를 참고하여 풀었다.

나의코드

def calculate_n(X,Y):
    n_set=set()
    
    for x in X:
        for y in Y:
            n_set.add(x+y)
            n_set.add(x-y)
            n_set.add(x*y)
            if y!=0:
                n_set.add(x//y)
                
    return n_set
    

def solution(N, number):
    
    if number==N:
        return 1
    
    answer = 0
    result={} # 횟수: 값들
    result[1]={N}
    
    
    for i in range(2,9):
        j=1
        temp_set={int(str(N)*i)} # 5,55,555
        while j<i:
            temp_set.update(calculate_n(result[j],result[i-j])) # -과 //은 a,b 와 b,a 의 순서에 따라 값이 다름 고려
            j+=1
            
        if number in temp_set:
            return i
        
        result[i]=temp_set
        
    return -1

 

---

 

참고하기