(프로그래머스 DP 문제 풀이) N으로 표현

DP(Dynamic Programming)

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번만 사용하여 표현할 수 있습니다.

def solution(N, number):
  # 인덱스가 N을 몇 번 사용했는지를 나타냄 ex) dp_table[1]: 1번 사용, d_table[4]: 4번 사용
  dp_table = [[]]
  for i in range(1, 9): # N 조건이자 사용 횟수 조건(8보다 크면 -1 리턴)
    case = []
    for j in range(1, i):
        for k in dp_table[j]: # j번 사용한 경우의 수 원소 iteration
          for l in dp_table[i - j]: # i-j번 사용한 경우의 수 원소 iteration
              case.append(k + l) # 더하기
              if k - l >= 0: 
                  case.append(k - l) # 빼기
              case.append(k * l) # 곱하기
              if l != 0 and k != 0:
                  case.append(k // l) # 나누기
    case.append(int(str(N) * i)) # 숫자를 그대로 이어 붙인 케이스 ex) 55, 555
  
    if number in case:
        return i
    dp_table.append(list(set(case)))
  return -1

해당 문제는 Level 3에 해당하는 DP 문제이다. 문제 설명을 얼핏 보면 간단해보이지만 사실상 그렇지 않고, 다이나믹 프로그래밍 특성상 코딩보단 수학 문제에 가까운 것 같다.

다이나믹 프로그래밍에서 먼저 고려해볼 문제는 1) 모든 가능한 경우의 수를 구하고, 이 리스트에서 정답을 찾는지 판단하는 것, 2) 아니면 누적의 개념을 생각해서 전 혹은 전전까지 과정을 바탕으로 현재 정답을 구할지 판단하면 된다.

위 문제는 1번에 해당하며 숫자 N을 가지고 만들 수 있는 모든 경우의 수를 구한 뒤 number가 여기에 속하는지 판단하여 결과를 출력하면 된다. 이때 문제 제한사항을 잘 살펴보면 힌트를 얻을 수 있는데, N이 1~9 사이에 있기 때문에 충분히 계산 가능하지 않을까 라고 추측해보자. 

여기까지 생각했다면 다음은 실제 구해보는 것이다. 항상 예시를 사용해서 처음부터 구해보면 좋다. 예를 들어, N=5, number=12일 때 계산 과정을 살펴보자.

N을 1번만 사용할 경우: 5 -> 1가지
N을 2번 사용할 경우: 55, 5+5, 5-5, 5x5, 5/5 -> 1가지
N을 3번 사용할 경우: 555, (5+5) + 5, (5-5) + 5, (5x5) + 5, (5/5) + 5
                            (5+5) - 5, (5-5) - 5, (5x5) - 5, (5/5) - 5
                            ...
                            (55) + 5, (55) - 5, (55) * 5, (55) / 5

N을 3번 사용할 경우를 자세히 보면, N을 1번 사용할 경우 + N을 2번 사용할 경우를 조합한 것임을 알 수 있다. 괄호로 친 것이 N을 2번 사용한 경우이며 각각에 N을 1번만 사용한 경우가 사칙연산으로 합쳐져 있다. 즉 N을 2번 사용한 경우의 각 원소마다 4가지 사칙연산이 적용되고, 모든 원소를 반복하면 된다.

코드 상에서 보이는 4개의 for문 로직을 단번에 이해하기는 쉽지 않다. 각 순서를 말로 풀어보자면...

N을 1번부터 8번 사용하는 것까지 모두 반복한다 -> 반복문이 돌다 4번 사용할 차례가 왔을 때, 1) 1번 사용한 경우와 3번 사용한 경우 조합, 2) 2번 사용한 경우와 2번 사용한 경우 조합으로 나눈다 -> 1)의 경우로 예를 들면, 1번 사용한 경우의 수 원소들과 3번 사용한 경우의 수 원소들 간의 조합을 구한다

이렇게 해서 구해진 모든 경우의 수 리스트에 찾고자 하는 number가 없다면(8번을 초과했다는 의미) -1을 리턴하고, 있다면 사용한 횟수를 리턴하는 것이다. 사용한 횟수는 i로 표시되는데, i번 사용해서 만든 모든 경우의 수를 구한 뒤에 항상 number가 있는지 체크한다.

사실 코드를 구현하지 못해, 다른 분들의 코드를 참고했음에도 이해하는 데 시간이 많이 걸렸다. 확실히 코딩은 평소에 훈련 시간이 많이 필요하지 않았을까라고 반성했다.