[프로그래머스] N으로 표현 [동적 계획법]

programmers.co.kr/learn/courses/30/lessons/42895#

코딩테스트 연습 - 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 합니다.

입출력 예

N	number	return
5	12	4
2	11	3

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

풀이

문제를 풀기 위해서는 모든 가능한 조합을 비교해봐야 합니다.

5를 n번 사용하여 만들 수 있는 수는 다음과 같습니다.

n	numbers
1	5
2	[10, 0, 25, 1, 55] => 범위
3	[[15, 5, 50, 2], [30, 20, 125, 5], [6, 4, 5, 0], [60, 50, 275, 11], 555] => 중복, 범위
4	...
5	...
6	...
7	...
8	...

n = 2일 때 numbers는 n = 1일 때 numbers와 n = 1일 때 numbers의 사칙연산 + NN으로 구성되며,
n = 3일 때는 n = 1일 때 numbers와 n = 2일 때 numbers의 사칙연산 + NNN으로,
n = 4일 때는 n = 1, n = 3의 사칙연산과 n = 2, n = 2의 사칙연산 + NNNN으로 구성되는 것을 확인할 수 있습니다.

N을 n 개 사용했을 때,
    i + j = n이 되는 순서 상관없이 중복되지 않는 (i, j)를 순회,
        N을 i 개 써서 생성할 수 있는 원소를 순회
            N을 j 개 써서 생성할 수 있는 원소를 순회
                사칙연산 => 중복, 범위 체크
                    찾고 있던 값이면 => return n
                    찾는 값이 아니면 => 해당 값은 N을 n번 사용하여 만들 수 있음을 저장

사칙연산을 통해 만들 수 없는 NNN과 같은 값은 N을 몇 번 사용한 수인지 미리 저장해줍니다.

 

MAX = 9
LIMIT = 32001

minimum = [MAX for _ in range(LIMIT)]
result = [[] for _ in range(MAX)]

operations = [
    lambda x, y: [x + y],
    lambda x, y: [abs(x - y)],
    lambda x, y: [x * y],
    lambda x, y: divmod(max(x, y), min(x, y)),
]
checks = [
    lambda x: x[0] < LIMIT,
    lambda x: x[0] > 0,
    lambda x: x[0] < LIMIT,
    lambda x: x[0] > 0 and x[1] == 0,
]

def solution(N, number):
    NNN = N
    for n, row in enumerate(result, start=1):
        if NNN == number:
            return n
        elif NNN >= LIMIT:
            break
            
        row.append(NNN)
        minimum[NNN] = n
        NNN = 10 * NNN + N
        
    for n in range(2, MAX):
        for i in range(n//2):
            j = n - i - 2
            for ele1 in result[i]:
                for ele2 in result[j]:
                    for operation, check in zip(operations, checks):
                        value = operation(ele1, ele2)
                        if not check(value) or minimum[value[0]] <= n:
                            continue
                        if value[0] == number:
                            return n
                        result[n-1].append(value[0])
                        minimum[value[0]] = n
                        
    return -1

operation과 check는 사칙연산 코드의 반복적인 부분이 많아 코드를 정리하며 추가한 부분이기 때문에 아래와 같은 식으로 풀어 사용하셔도 무방합니다.

MAX = 9
LIMIT = 32001

minimum = [MAX for _ in range(LIMIT)]
result = [[] for _ in range(MAX)]

def solution(N, number):
    NNN = N
    for n, row in enumerate(result, start=1):
        if NNN == number:
            return n
        elif NNN >= LIMIT:
            break
            
        row.append(NNN)
        minimum[NNN] = n
        NNN = 10 * NNN + N
        
    for n in range(2, MAX):
        for i in range(n//2):
            j = n - i - 2
            for ele1 in result[i]:
                for ele2 in result[j]:
                    add = ele1 + ele2
                    if add < LIMIT and minimum[add] > n:
                        if add == number:
                            return n
                        result[n-1].append(add)
                        minimum[add] = n

                    sub = abs(ele1 - ele2)
                    if sub > 0 and minimum[sub] > n:
                        if sub == number:
                            return n
                        result[n-1].append(sub)
                        minimum[sub] = n

                    mul = ele1 * ele2
                    if mul < LIMIT and minimum[mul] > n:
                        if mul == number:
                            return n
                        result[n-1].append(mul)
                        minimum[mul] = n

                    dst1, dst2 = max(ele1, ele2), min(ele1, ele2)
                    div, mod = divmod(dst1, dst2)
                    if mod == 0 and div > 0 and minimum[div] > n:
                        if div == number:
                            return n
                        result[n-1].append(div)
                        minimum[div] = n
    return -1