[코딩테스트] 프로그래머스 - N으로 표현 (Lv.3) in Python

숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return.

 

예시:

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

 

12를 5와 사칙연산만으로 표현.

이 중 5를 가장 적게 쓴 경우는 4번 쓴 경우이므로, 4를 반환.

 

다만, N을 9번 이상 사용해야할 경우 -1을 반환.

 

프로그래머스 강의를 바탕으로 해답을 작성했습니다.

 

 

더 자세한 설명 - programmers.co.kr/learn/courses/30/lessons/42895

 

동적계획법 (Dynamic Programming)

- 고려해야할 범위가 너무 크므로, 주어진 최적화 문제를 재귀적으로, 부분 문제로 나누어, 해를 조합하여 전체 문제의 해답을 찾아내는 방법

 

- 탐색해야할 범위를 동적으로 결정하면서 탐색 범위를 줄여나감.

 

풀이

1. 

N을 한 번 사용해서 만들 수 있는 수들 ... (a)

N을 두 번 사용해서 만들 수 있는 수들 - (a) 이용 ... (b)

N을 세 번 사용해서 만들 수 있는 수들 - (b) 이용 ... (c)

 

의 방식으로 범위를 줄여나간다.

 

ex. N = 5

N을 한 번 사용해서 만들 수 있는 수들 ... 5

N을 두 번 사용해서 만들 수 있는 수들 ... 55, 5 + 5 = 10, 5 - 5 = 0, 5 * 5 = 25, 5 / 5 = 1

N을 세 번 사용해서 만들 수 있는 수들

... 555,

   55 + 5 = 60, 55 - 5 = 50, 55 * 5 =275, 55 // 5 = 11,

   (5 + 5) + 5 = 15, 10 - 5 = 5, 10 * 5 = 50, 10 // 5 = 2,

   (5 - 5) + 5 = 5, 0 - 5 = -5, 0 * 5 = 0, 0 // 5 = 0,

   (5 * 5) + 5 = 30, 25 - 5 = 20, 25 * 5 = 125, 25  // 5 = 5, 

   (5 / 5) + 5 = 6, 1 - 5 = -4, 1 * 5 = 5, 1  // 5 = 0, 

   5 + (5 + 5) = 15, ...  [여기부터는 (-)와 (//)의 결과가 달라지므로 이 또한 고려해야함]

   5 + (5 - 5) = 5, ...

   5 + (5 * 5) = 30...

   5 + (5//5) = 6 ...

   중복된 수를 제외하면:

   {555, 60, 55, 275, 11, 15, 5, 50, 2, -5, 0, 30, 20, -20, 125, 6, -4, 4}

 

 

따라서,

(n) "x" * n

(1) +-/* (n-1)

(2) +-/* (n-2)

...

(n-1) +-/* (1)

의 식으로 생각할 수 있다.

 

이 때, n은 문제에 주어진대로 최대 8임을 기억.

 

s = [set() for x in range(8)] 

로, N을 1번 - 8번 쓸 때 나올 수 있는 숫자들을, 중복없이 담아주는 set들의 list를 일단 정의하고 시작한다.

 

 

 

파이썬 구현

def solution(number, N):
    s = [set() for x in range(8)]
    
    # N을 i번 반복해서 만들 수 있는 수 먼저 s에 넣어줌
    # 예외처리 보다 쉽게하기 위함
    for i,v in enumerate(s, start = 1):
    	num = int(str(N)* i)
        if num == number:
        	return i
        v.add(num)
        
    # i번 사용할 수들 집합
    # NOTE.s[i]은 N을 i번 사용한 수들 집합
    for i in range(1, len(s)):
    	# i = 1이면 0번,
        # i = 2이면 0번, 1번, ..
        # 사용한 숫자들을 꺼내도록
        for j in range(i):
            for op1 in s[j]:
                for op2 in s[i-j-1]:
                    s[i].add(op1 + op2)
                    s[i].add(op1 - op2)
                    s[i].add(op1 * op2)
                    
                    if op2 != 0:
                    	s[i].add(op1 // op2)
        if number in s[i]:
            return i + 1
 	
    return -1
                    
                

 

중첩문이 정말 많지만, set을 이용해 중복된 값을 없애주니 생각보다는 시간이 오래 걸리지 않는다.