N으로 표현
레벨3, 동적계획법
처음으로 직접 풀게 된 DP, 동적계획법 문제입니다.
이전에 뭣모르고 알고리즘 책 부터 사서 읽어 볼 때, 다른 문제는 그래도 어떻게 풀면 되겠구나 싶었는데, 정말 답도 안나오고 모르겠던 유형이 아마 DP가 아니었나 싶습니다.
1. 문제 설명
아래와 같이 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 함수를 작성하세요.
문제의 요구사항은 주어진 하나의 숫자를 가지고, 사칙연산만을 이용하여 목표 숫자를 만들되, 이 때 주어진 숫자를 가장 적은 횟수로 사용하는 경우의 사용 횟수를 출력하는 문제입니다. 이때, 숫자를 옆으로 늘어놓는(5 2개를 활용하여 55를 만드는)경우도 허용됩니다.
2. 제한사항
1. N은 1 이상 9 이하입니다.
2. number는 1 이상 32,000 이하입니다.
3. 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
4. 최솟값이 8보다 크면 -1을 return 합니다.
3. 사고과정 / 나의 풀이
처음 문제를 접했을 때에는 정말 어떻게 풀어야 할 지 감도 오지 않았습니다. 다른 유형의 문제들은 그래도 이전에 접해본 적이 있었고, 자료구조나 문법적으로 대략 '아, 이렇게 하면 되겠구나' 하는 것이 보였는데, 저같은 경우는 이런 문제는 정말,, 어떻게 풀어야 할 지 감이 오지 않았습니다.
정확히는 두 가지 이유로 정말 막막했습니다.
첫째는, 내가 직접 풀려고 했을 때, 가장 작은 경우의 수를 어떤 규칙으로 찾아내야 하는지 전혀 모르겠었고 둘째로는, 어떻게 컴퓨터가 이런 문제를 풀게 만들지도 모르겠는, 말그대로 실마리조차 보이지 않는 상태였습니다.
그래서 멍하니 문제를 다시 읽어보다가, 최솟값이 8보다 크면 -1을 리턴하라는 조건을 보고 나서야, 이건 다 늘어놔야 하는건가 싶은 생각이 들었습니다. 이전에 봤던 알고리즘 문제중 하나가, 사칙연산으로 가장 큰 수를 만드는 것이었는데 아마 이런 비슷한 방법을 썼던 것 같았습니다
그래서 숫자 하나를 정해서 생각 해 본 내용은 아래와 같습니다.
1. 숫자를 1번~8번 썼을 때 가능한 모든 경우를 구하는 것 같다.
2. 1번 썼을 때 가능한 숫자는 당연히 한가지(5)로 정해져있다.
3. 2번 썼을 때 가능한 숫자는, 55, 5+5 = 10, 5-5 = 0, 5//5 = 1, 5*5 = 25로 5가지 경우가 있다. (0, 1, 10, 25, 55)
4. 그런데 2같은경우는 22, 2+2 = 4, 2-2 = 0, 2//2 = 1, 2*2 = 4로 5가지 경우지만, 숫자는 4개이다. (0, 1, 2, 22) 즉, 숫자의 수에는 일반화할 규칙이 없고, 숫자를 경우의 수에 맞게 바로 만들어서 사용 할 수 없다..
5. 그렇다면 이전에 만든 숫자를 가져다 쓸 수 있을 것 같다.
6. 3번 썼을 때를 한번 더 보면, 555, 5+5+5, 5+55, 55+5, 5-5-5, 5-55, 55-5... 등의 숫자가 나온다.
여기서 사실 망한건가.. 어떻게 해야하지? 했는데, 조금 풀어서 자세히 보면 아래와 같다
(5+5)+5 = 10 + 5, 5-(5-5) = 5-0..
7. 결국 n번째 횟수에서 연산은 n-1번째에 만들어진 숫자들에 대한 사칙연산만으로도 모두 표시가 가능할 것 같다.
이것을 코드로 표현하자면,
def solution(N, number):
SET = []
# 숫자 만들기
for i in range(1, 9): # 1~8까지
nums = set()
nums.add(int(str(N) * i))
for j in range(0, i-1): # 2~8인 경우에 대해서 j 지정
for a in SET[j]: # 지정된 j를 활용해서 앞에서 j번째
for b in SET[-j-1]: # 뒤에서 j번째 수 선정
nums.add(a + b)
nums.add(a - b)
nums.add(a * b)
nums.add(a // b)
SET.append(nums)
# 순회하며 해당 숫자 발견 시 리턴
for i in range(len(SET)):
if number in SET[i]:
return i+1
# 8까지 순회했을 때, 발견 못하면 -1 리턴
return -1
풀었나 싶었는데, 역시나 에러 등장.. ZeroDivisionError.. 아.. 나누기 하는 과정에서 0이 있다는 것을 놓쳤습니다. 이를 처리해서 아래처럼 다시 제출 해 봅니다.
def solution(N, number):
SET = []
# 숫자 만들기
for i in range(1, 9): # 1~8까지
nums = set()
nums.add(int(str(N) * i))
for j in range(0, i-1): # 2~8인 경우에 대해서 j 지정
for a in SET[j]: # 지정된 j를 활용해서 앞에서 j번째
for b in SET[-j-1]: # 뒤에서 j번째 수 선정
nums.add(a + b)
nums.add(a - b)
nums.add(a * b)
try:
nums.add(a // b)
except:
pass # b가 0인경우 pass
SET.append(nums)
# 순회하며 해당 숫자 발견 시 리턴
for i in range(len(SET)):
if number in SET[i]:
return i+1
# 8까지 순회했을 때, 발견 못하면 -1 리턴
return -1
일단 통과는 했습니다. 그런데 전체 순회 후, 다시 한 번 순회하며 비교하는 방식보다는, 어차피 SET에 넣기 전에 nums단계에서 비교하는 것이 더 빠르지 않을까 싶습니다.
def solution(N, number):
SET = []
for i in range(1, 9):
nums = set()
nums.add(int(str(N) * i))
for j in range(0, i-1):
for a in SET[j]:
for b in SET[-j-1]:
nums.add(a + b)
nums.add(a - b)
nums.add(a * b)
try:
nums.add(a // b)
except:
pass
if number in nums:
return i
SET.append(nums)
return -1
이렇게 나름 깔끔한 코드로 문제를 풀게 됐습니다.
3. 다른 사람의 풀이
맨 위, 첫번째 풀이
def solution(N, number):
S = [{N}]
for i in range(2, 9):
lst = [int(str(N)*i)]
for X_i in range(0, int(i / 2)):
for x in S[X_i]:
for y in S[i - X_i - 2]:
lst.append(x + y)
lst.append(x - y)
lst.append(y - x)
lst.append(x * y)
if x != 0: lst.append(y // x)
if y != 0: lst.append(x // y)
if number in set(lst):
return i
S.append(lst)
return -1
풀이 과정은 거의 비슷한 것 같습니다. 다만 다른 부분은 x와 y의 순서도 고려해 주신 점이 다르네요.
제 풀이에서는 j가 정방향으로 한 번, 역방향으로 한 번 끝까지 돌면서 전체를 순환하였는데, 위 풀이에서는 X_i를 이용해서 중앙지점까지만 순회를 돌게 됩니다.
다시 말해, 제 풀이는 순회부분에서 일정 낭비가 있지만, 그 과정에서 자연스럽게 교환법칙에 의한 예외를 처리해주는 것이고, 이 풀이를 작성 해 주신 분 께서는 순회를 위한 낭비를 줄이는 대신, 추가적인 연산을 해 주셨다고 보면 될 것 같습니다.
answer = -1
def DFS(n, pos, num, number, s):
global answer
if pos > 8:
return
if num == number:
if pos < answer or answer == -1:
#print(s)
answer=pos
return
nn=0
for i in range(8):
nn=nn*10+n
DFS(n, pos+1+i, num+nn, number, s+'+')
DFS(n, pos+1+i, num-nn, number, s+'-')
DFS(n, pos+1+i, num*nn, number, s+'*')
DFS(n, pos+1+i, num/nn, number, s+'/')
def solution(N, number):
DFS(N, 0, 0, number, '')
return answer
이 코드는 재귀를 썼다는 점에서 가장 신기해서 가져와 봤습니다. pos가 8보다 작을때에만 작동하는 dfs함수를 통해 모든 경우의수를 다 계산하게됩니다.
아무래도 문제를 접하고 사람들이 가장 생각하기 쉬운 방향이다보니, 저는 이 풀이가 직관적으로는 더 와닿았습니다. 다만 확실히 효율성 면에서는 떨어지는 풀이인것같습니다.
from itertools import product
def solution(N, number):
return solve(N, 0, number, 8, {})
def solve(digit, current, target, chance, cache):
key = (digit, current, chance)
# Try to reuse previous calculation
if key in cache:
return cache[key]
# Solved?
if current == target:
return 0
nums = [
(1, 1 * digit),
(2, 11 * digit),
(3, 111 * digit),
(4, 1111 * digit),
(5, 11111 * digit),
(6, 111111 * digit),
(7, 1111111 * digit),
(8, 11111111 * digit),
]
ops = [
('+', lambda a, b: a + b),
('-', lambda a, b: a - b),
('*', lambda a, b: a * b),
('/', lambda a, b: a // b),
]
# Recursively try candidate operations
spents = []
for (cost, num), (label, op) in product(nums, ops):
if chance < cost:
continue
#print(f'{current} {label} {num} = {op(current, num)}')
spent = solve(digit, op(current, num), target, chance - cost, cache)
if spent == -1:
continue
spents.append(spent + cost)
# Done
if len(spents) == 0:
result = -1
else:
result = min(spents)
# Save calculation for later reuse
cache[key] = result
return result
이 풀이의 경우는 일단 (가장 있어보이고..) 체계적이고, ops를 변수에 담아서 활용했다는 점과 product를 활용해 모든 경우의수를 고려했다는 점이 재미있어서 가져와보았습니다.
