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

특히 DP의 경우 점화식이나 수학적인 패턴이 나오는데 이것을 파악하기 위해서 케이스들을 나열하는 습관을 들여볼 필요가 있을거 같다.

생각보다 간단한 문제였는데 풀이를 봐버린게 아쉽다. 

 

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

프로그래머스

문제 설명

아래와 같이 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 합니다.

---

해설

문제를 푸는데 가장 핵심적인 논리는 a + a = A, b + b = B 일때 A + B = a + a + b + b의 개념이다.

굉장히 단순하고 또 당연한 개념인데 이상하리 생각이 안난 문제였다.

예를 들어 

N = 5

사용 회수 1 일때 [5]

사용 횟수 2 일때 [55, 5 + 5 , 5 / 5 , 5 - 5, 5 * 5]

사용 횟수 3 일때 [555, 5 + 5 + 5, (5 + 5) / 5 , 5 + 5/5, 5 - 5 + 5 .....]

일때 3번째를 다르게 표현하면 다음과 같다.

5 +5 + 5 -> 5 + 5(사용횟수 2일때의 숫자) + 5(사용횟수 1일때의 숫자)

(5 + 5) / 5 -> 5 + 5(사용횟수 2일때의 숫자) / 5(사용횟수 1일때의 숫자)

5 + 5/5 -> 5(사용횟수 1일때의 숫자) + 5/5(사용횟수 2일때의 숫자)

간단 하게 말하면 사용횟수 n일 경우 

(n - 1, 1) ( n - 2, 2) ........ (1 , n - 1)의 조합을 가지게 된다.

 

def solution(N, number):

    setDp = [[0],[N]]
    #step == 0
    #0
    #step == 1
    #N
    #step == 8이면 (7,1) (2,6) ( 3,4)... (1,7)

    if N == number:
        return 1

    for step in range(2,9):
        tempSet = set([int(str(N) * step)]) # 5, 55, 555 등 삽입
        x = 1
        while x < step:
            result = calculate(setDp[step - x],setDp[x])
            tempSet.update(result)
            x += 1

        if number in tempSet: #현재 단계에서 원하는 숫자 있으면 바로 return
            return step
        setDp.append(list(tempSet))

    return -1




def calculate(lh,rh):
    mySet = set()
	
    # 예를 들어step 5 단계 일때
    # lh는 1번 사용되었을때 생성된 숫자
    # rh는 4번 사용되었을때 생성된 숫자
    # 결국 값을 사칙연산하면 5번 사용하게 된 경우나 마찬가지
    for l in lh:
        for r in rh:
            mySet.add(l + r)
            mySet.add(l * r)
            mySet.add(l - r)
            if r != 0:
                mySet.add(l // r)

    return mySet