[동적계획법] N으로 표현

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

프로그래머스

---

문제 설명
아래와 같이 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번만 사용하여 표현할 수 있습니다.

---

동적 계획법이라는 단어가 사실 잘 안 와닿는 단어라고 생각합니다. 특히 이런 문제들은 보면 분할 정복법이랑 비슷한게 대부분이거든요.

피보나치 수열이 대표적인 동적 계획법 문제입니다. 아래의 구조를 가지거든요.

fib(5) = fib(4) + fib(3) = [fib(3) + fib(2)] + [fib(2) + fib(1)] + ...

이렇게 큰 문제를 작게 쪼개서 푸는 방법이 바로 동적 계획법입니다.

"어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘인 거죠.

---

이 문제 같은 경우는 숫자 N을 사용해서 특정 숫자 number를 만드는 최소의 개수 k를 구하는 문제입니다.

동적 계획법을 적용해야 하는데, 더 작은 문제로는 어떻게 쪼갤까요?

 

여러 시행착오가 있었는데 넘어가고 일단 답부터 말해보면, 숫자 N을 i번 사용한 경우와 j번 사용한 경우를 합치면 총 (i + j)번 사용한 것과 같습니다.

다시 말해 "(i + j)번 사용해서 만들 수 있는 수" = "i번 사용해서 만들 수 있는 수" + "j번 사용해서 만들 수 있는 수"인 거죠.

 

따라서 우리는 숫자 N을 x(1부터 8)번 사용해서 만들 수 있는 기본 수를 구하고, 이 기본 수들을 기반으로 만들 수 있는 수들을 계산하면 됩니다.

 

순서를 맞춰서 문제를 풀어보겠습니다.

---

1. 기본 수 설정

# 숫자를 N번 써서 만들 수 있는 기본 숫자들
memo = [set() for _ in range(9)]
for i in range(1, 9):
    memo[i].add(int(str(N) * i))

이 숫자들은 단순히 숫자를 나열해서 만들 수 있는 모든 숫자들입니다.

N이 1이라면, 1 - 11 - 111 - 1111 - ... 이런 형식인 거죠. 사칙연산 없이 만들 수 있는 기본 수입니다.

 

2. 사칙연산을 사용한 수 설정

# 숫자를 i번 쓰는 경우 = 숫자를 j번 쓰는 경우 + 숫자를 (i - j)번 사용하는 경우
for i in range(1, 9):
    for j in range(1, i):
        for op1 in memo[j]:
            for op2 in memo[i - j]:
                # 사칙연산 결과를 저장한다.
                memo[i].add(op1 + op2)
                memo[i].add(op1 - op2)
                memo[i].add(op1 * op2)
                if op2 != 0:
                    memo[i].add(op1 // op2)
    # i번째에서 숫자가 등장하면 최소값이다.
    if number in memo[i]:
        return i

왜 굳이 (i - j)로 설정해서 값을 계산하는지 궁금하실 수 있는데, 사용할 수 있는 최대 횟수가 8로 정해져있기 때문입니다. 겸사겸사 중복 계산도 피할 의도도 있고요. 이 과정에서 모든 사칙연산 결과를 계산해서 i번째에 추가합니다.

 

만약 추가된 i번째에 해당하는 숫자가 있다면 이 i가 최솟값임이 보장되므로 i를 반환합니다.

 

3. 예외 처리

예외 처리라고 말은 해두었지만 사실 return -1을 추가하면 됩니다.

모든 i에 대해서 탐색을 했지만 number가 발견되지 않았을 때, 즉 최대 횟수인 8 안에서는 값이 등장하지 않은 경우입니다.

문제의 제한사항인

최솟값이 8보다 크면 -1을 return 합니다.

에 따라서, 마지막 줄에 추가해줍시다.

---

최종 코드는 다음과 같습니다.

def solution(N, number):
    # N이 곧 number일 때
    if N == number:
        return 1
    
    # 숫자를 N번 써서 만들 수 있는 기본 숫자들
    memo = [set() for _ in range(9)]
    for i in range(1, 9):
        memo[i].add(int(str(N) * i))
    
    # 숫자를 i번 쓰는 경우 + 숫자를 j번 쓰는 경우
    for i in range(1, 9):
        for j in range(1, i):
            for op1 in memo[j]:
                for op2 in memo[i - j]:
                    # 사칙연산 결과를 저장한다.
                    memo[i].add(op1 + op2)
                    memo[i].add(op1 - op2)
                    memo[i].add(op1 * op2)
                    if op2 != 0:
                        memo[i].add(op1 // op2)
        # i번째에서 number가 발견되는지 확인
        if number in memo[i]:
            return i
        
    # 모든 i에서 발견되지 않는다면 -1 반환
    return -1

큰 문제를 어떻게 작게 쪼갤지를 고민하는 게 중요한 알고리즘이라 생각이 드네요.