[Programmers] - N으로 표현 (동적계획법) with Python

📎 간략한 문제 정리

• 주어진 숫자 N을 반복 활용해서 사칙연산을 통해 number를 만듭니다. number를 만들기 위해 필요한 N의 최소 개수를 출력합니다.

📈 문제 분석

• N을 최대로 활용할 수 있는 개수가 8개로 한정 되어있어 보다 쉽게 풀이 가능한 문제입니다. 단순히 5로만 연산하는 것이 아니라 5를 2개 사용할 경우 55가 되기 때문에 상황 설계를 엄밀히 할 필요가 있습니다. 개수만 늘려가며 사칙연산의 경우를 추가하면 안됩니다.

🙋‍♂️ 내가 처음 생각한 해결 방법

• 그래프적으로 문제를 인식하여 Pruning을 생각해보았지만 뺄셈 연산이나 나누기 연산처럼 값이 작아지는 경우가 있기 때문에 Pruning 할 수 없었습니다. 포인트는 특정 개수의 N으로 만들 수 있는 모든 경우의 수를 기록하고, 그 안에 해답이 있는지 찾는 문제입니다. 결국 Brute Force처럼 모든 경우를 탐색하지만 그 결과물은 기록하여 재활용하는 DP 형식으로 구현됩니다.

💻 풀이한 코드

def solution(N, number):
    cache = [0, {N}]
    if N == number: return 1
    for i in range(2, 9):
        case = {int(str(N)*i)}
        for j in range(1, i//2 + 1):
            for x in cache[j]:
                for y in cache[i-j]:
                    case.add(x+y)
                    case.add(x*y)
                    case.add(x-y)
                    case.add(y-x)
                    if x != 0: case.add(y//x)
                    if y != 0: case.add(x//y)
        if number in case: return i
        cache.append(case)
    return -1

📝 해결 과정에서 만난 문제, 고민들

• j의 범위가 i//2 + 1인 이유를 이해하기 힘들었습니다. 생각해보면 다음과 같습니다. 예를 들어, N을 5번 사용하는 경우를 생각해보면

  1. (N을 1번 사용하는 경우), (N을 4번 사용하는 경우) 의 조합
  2. (N을 2번 사용하는 경우), (N을 3번 사용하는 경우) 의 조합
  3. (N을 3번 사용하는 경우), (N을 2번 사용하는 경우) 의 조합
  4. (N을 4번 사용하는 경우), (N을 1번 사용하는 경우) 의 조합
  5. N을 5번 사용하는 경우

  로 나눌 수 있습니다. 하지만 생각해보면 2번의 과정과 3번의 과정은 같은 결과이고, 1번의 과정과 4번의 과정이 같은 결과이므로 절반만 확인해도 같은 결과가 나옵니다. 다시 말하면, j 반복문 아래에 x, y 반복 구조에서 cache[j], cache[i-j]가 의미하는 것이 N을 j번 활용하여 만들 수 있는 수의 경우(위의 예시 2번에서 j가 2이면)와 i-j번(위의 예시 2번에서 i-j는 3번)은 j가 i//2를 넘어가는 순간 완전히 같은 것이 되고, 아래 연산은 정확히 두 연산을 대칭적으로 활용하기 때문에 i//2 이후를 체크할 이유가 없습니다.

• N이 연속적으로 사용된 수(예를 들어 5가 3번 사용되면 '555')를 반복문 안에 넣을 생각을 했었습니다. 굳이 j가 1부터 시작하는게 아니라 0번부터 시작하면 되지 않을까 하는 생각을 해보았지만 그런 구조로 작성할 수 없는 이유는 cache에는 아직 j가 i일 때(예시 기준으로 5가 3번 사용되었을 때) cache가 없기 때문에 index 에러가 발생할 수 밖에 없고, 미리 넣는다면 나중에 다시 그 값을 갱신해주어야 하기 때문에 불필요한 연산이 추가됩니다. 그래서 위와 같이 N을 연속적으로 사용하는 부분을 우선적으로 만들어주고(위의 예시에서 5번 케이스) 나머지 조합을 만들어주어 추가하는 구조로 작성했습니다.

• int를 연속적으로 사용할 때 int로서 접근하여 1, 11, 111, 1111... 을 곱해준다고 생각할 수 있지만, Python은 String에 대한 연산이 상대적으로 쉽고 잘 되어있어 String으로 연산해 준 후 다시 int로 변환해주는 것이 더 효율적입니다.

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