문제 설명
입력으로 숫자 N, number가 주어질 때 숫자 N과 사칙연산만 사용해서 number를 표현할 때 N의 사용 횟수의 최솟값을 구해야 한다.
접근
N=5, number = 12라고 해보자. 다음과 같이 12를 표현할 수 있다.
12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5
첫 번째 경우에서는 5를 6번 사용하였고, 두 번쨰째는 5번, 세 번째는 4번 사용해서 표현되었다.
따라서 N의 사용 횟수의 최솟값은 4가 된다.
입력으로 주어지는 숫자 number는 최대 32000이기 때문에 모든 경우를 직접 다 찾기가 힘들다.
그렇다면 어떻게 문제를 풀어야 할까?
한 번 연산을 쪼개보자.
12 = 5 + 5 + (5 / 5) + (5 / 5) 연산에서 다음과 같이 두 부분으로 나누어보았다.
12 = {5 + 5} + {(5 / 5) + (5 / 5)}
즉, 숫자 5를 6개를 사용해서 만든 수를 2개를 사용해서 만든 수와 4개를 사용해서 만든 수를 사칙연산(+)을 한 수로 보았다.
오른쪽 부분((5 / 5) + (5 / 5))을 또 두 부분으로 나눠보면 다음과 같다.
2 = {(5 / 5)} + {(5 / 5)}
즉, 숫자 2를 4개를 사용해서 만든 수를 2개를 사용해서 만든 수와 2개를 사용해서 만든 수를 사칙연산(+)을 한 수로 보았다.
이런 식으로 어떤 계산 식을 부분 식으로 나눠서 보게 되면 DP(dynamic programming)로 접근해서 풀 수 있게 된다.
문제 풀이
DP로 접근하기 위해서는 점화식이 필요하다. 점화식을 다음과 같이 정의해 보았다.
s[i]: N을 i개 사용해서 만들 수 있는 수들의 집합이라고 하면
s[i] = U(j = 1, 2, …, i-1, op = +, -, *, /){s[j] op s[i-j]} U {NN…N(i번 반복)}
즉, 숫자 N을 i개를 사용해서 만들 수 있는 수는
- N을 j개 사용해서 만들 수 있는 수(j = 1, 2, …, i-1)와 i - j개 사용해서 만들 수 있는 숫자를 사칙연산(+, -, *, or /)한 수
- N을 n개 연속으로 붙여서 만들어지는 수(NNNN…N(i번 반복))
이 두 가지로 구성된다.
그리고 문제에서 최솟값이 8보다 크면 -1을 return 하라고 했으므로
s[1]부터 s[8]까지 차례대로 DP 테이블을 갱신해주면 된다.
구현 코드
def solution(N, number):
# i 번째 set은 N을 i개 사용해서 만들 수 있는 숫자들이 담김
s = [set() for i in range(9)]
# N 숫자가 연속으로 i개 붙어있는 수들을 각 집합에 담아줌
# ex) s[5]: N=7을 5개 사용해서 만들 수 있는 숫자들의 집합 -> 77777을 넣어줌
for i in range(1, 9):
s[i].add(int(str(N) * i))
# bottom up 방식으로 DP 알고리즘 수행
for i in range(1, 9):
# N을 i개 사용해서 만들 수 있는 숫자들은
# 위에서 담아준 NNNN...N(i번 반복) 숫자와
# N을 j개 사용해서 만들 수 있는 숫자 op i - j개 사용해서 만들 수 있는 숫자로 나타낼 수 있음
# op(+, -, *, /), j=1,2,..., i-1
for j in range(1, i):
for a in s[j]:
for b in s[i - j]:
s[i].add(a + b)
s[i].add(a - b)
s[i].add(a * b)
if b != 0:
s[i].add(a // b)
# s[i] 집합에 들어갈 모든 원소를 집어넣은 후
# number가 s[i]에 있으면(N을 i개 사용해서 number를 표현할 수 있음)
# i(N 사용 횟수의 최솟값) return
if number in s[i]:
return i
# N을 최대 8개 사용해서도 number를 만들 수 없는 경우
return -1