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

문제

---

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

https://school.programmers.co.kr/learn/courses/30/lessons/42895?language=python3# 

프로그래머스

 

문제 이해

---

문제 설명

아래와 같이 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. VFS

• Queue를 만들어 현재 있는 값을 갱신시켜 갈 수 있는 경우 탐색
• 55+(5*5) = 80 인 경우와 같이 뒤에 괄호가 있는 경우에 대해 문제가 발생

2. DP

• 55+(5*5) 는 5를 2번 사용하여 만들 수 있는 경우 5를 2번 사용하여 만들 수 있는 경우로 만들 수 있다.
• 이와 같은 접근 방법으로 n번을 사용하여 만들 수 있는 값은 n-i로 만든 경우 + i로 만드는 경우이다.

알고리즘 = DP

---

1. 총 8가지의 경우의 수를 미리 초기화

2. n=2~8까지는  n번을 사용하여 만들 수 있는 값은 n-i로 만든 경우 + i로 만드는 경우의 수를 추가

3. 요청 받은 값이 현재 리스트에 존재한다면, 종료

4. 없다면 return -1 반환

 

코드

---

1. VFS 접근

# Programmers-N으로 표현
from collections import deque
import sys
size = 300000
def solution(N, number):
    answer = -1
    dp = [sys.maxsize]*(size+1)
    dp[N] = 1 

    q = deque()
    q.append((N,1))
    if N==number:
        return 1

    while q :
        current,cnt=q.popleft()
        
        if current==number:
            return cnt
        if cnt>=8:
            continue
        
        #1. 곱셈
        if current*N <= size and dp[current*N]>cnt+1 :
            q.append((current*N,cnt+1))
        #2. 나눗셈
        if current%N == 0 and dp[current//N]>cnt+1 :
            q.append((current//N,cnt+1))
        #3. 빼기
        if current-N >= 0 and dp[current-N]>cnt+1:
            q.append((current-N,cnt+1))
        #4. 덧셈
        if current+N <= size and dp[current+N]>cnt+1:
            q.append((current+N,cnt+1))
        #5. 숫자 붙이기
        if int(str(current)+str(N)) <= size and dp[int(str(current)+str(N))]>cnt+1:
            q.append((int(str(current)+str(N)),cnt+1))
    return answer

N=5
number=80
print( solution(N,number) )

2. DP

# Programmers-N으로 표현
def solution(N, number):
    dp = [ set() for _ in range(9) ]

    for i in range(1,9):
        temp=set()
        temp.add( int(str(N)*i) )
        
        for j in range(i):
            for x in dp[j]:
                for y in dp[i-j]:
                    temp.add(x*y)
                    temp.add(x+y)
                    temp.add(x-y)
                    if y!=0:
                        temp.add(x//y)
        if number in temp:
            return i
        dp[i]=temp
    
    return -1

N=5
number=31168
print( solution(N,number) )