출처
https://school.programmers.co.kr/learn/courses/30/lessons/42895#
문제
N으로만 사칙연산을 활용하여 원하는 숫자를 만들때, 최소한의 갯수로 만드는 문제이다.
접근 방법
문제 조건에 N이 8 초과일 경우 -1을 반환하라고 되어있다. 그렇다면 우리는 최소 1번부터 8번까지만 살펴보면 된다.
DP문제로 접근을 하여 어떤 결과를 저장하여 다음 연산에 적용하면 될까..?라는걸 고민하다가 문득 든 생각은 1번부터 8번 사용했을때 까지 전부 계산을 하도록 하고 중간 단계를 저장해서 봐야겠다였다. 어떻게보면 완전 탐색처럼 모든 경우를 탐색하는것도 맞는것 같다. (완전탐색 + DP)의 느낌이다.
N을 한 번 사용하면 어떤일이 생길까?
1번 사용해 만들 수 있는 경우의 숫자는 [5] 하나 이다.
그렇다면 2번 사용했을때를 계산할 때는 어떻게 하는가?
1번 사용한 배열 + (사칙연산) + 1번 사용한 배열 또는 Nx2번반복 으로 만들어 [55, 5*5, 5-5, 5+5, 5//5]이 된다.
그렇다면 3번은? 2번사용해 만든 배열과 1번 사용해 만든 배열의 모든 원소를 사칙연산으로 조합하면 만들 수 있을 것이다
[555, 5*55, 5-55, 5+55, 5/55, 5*5*5, 5*(5/5), 5*(5+5), 5*(5-5), 5-(5*5), 5-(5/5) ................. 55*5, 55-5,55/5..............................]
4번의 경우는 [1번 사용] and [3번사용], [2번 사용] and [2번 사용] 의 조합이 가능 할 것이다. 이런식으로 하위 단계의 결과를 계속해서 사용하여 상위 단계의 결과를 계산하는 DP방식을 적용하면 된다.
풀이
- 연산을 해나가다보면 중복된 연산결과가 저장되는 경우가 생길 수 있다. 그래서 DP배열은 8개 선언하되, 내부 계산결과는 파이썬의 set() 집합 자료형을 사용하여 중복된 결과는 자동으로 제거되게 한다.
- 마지막에 필요없는 0을 제거해준다.
- 나누기에는 0이 들어가지 않도록 하여 에러를 방지해주고, 빼기의 경우 음수가 들어가지 않도록 해준다.
- 이중 for문을 사용하여 모든 배열의 조합을 계산해준다.
코드
def solution(N, number):
dp = [{}]
dp.append({N})
answer = 9
if N == number:
return 1
for i in range(2, 9):
tmp = set()
tmp.add(int(str(N) * i))
for x in range(1, i//2+1):
for j in dp[i-x]:
for k in dp[x]:
if j-k >= 0:
tmp.add(j-k)
if k-j >= 0:
tmp.add(k-j)
tmp.add(j+k)
tmp.add(j*k)
if k != 0:
tmp.add(j//k)
if j != 0:
tmp.add(k//j)
tmp.discard(0)
dp.append(tmp)
if number in tmp:
print(i)
answer = i
break
if answer > 8:
return -1
else:
return answer