from itertools import product
def solution(N, number):
d = [[] for _ in range(9)]
if N == number : return 1
d[1] = [N]
d[2].extend(list(set([10*N+N, N+N, N-N, N*N, N//N])))
if number in d[2] : return 2
for i in range(3, 9) :
d[i].extend([int(str(N) * i)])
for j in range(1, int(round(i/2))+1) :
for k in product(d[j], d[i-j]) :
t1 = k[0] + k[1]
t2 = k[0] - k[1]
t3 = k[1] - k[0]
t4 = k[0] * k[1]
if k[0] != 0 and k[1] != 0 :
t5 = k[1] // k[0]
t6 = k[0] // k[1]
else : t5 = t6 = 0
tmp = list(set([t1, t2, t3, t4, t5, t6]))
if number in tmp :
return i
else :
d[i].extend(tmp)
return -1
처음엔 이게 어떻게 dp 로 풀릴까 막막했는데, 많은 생각 끝에 아이디어를 떠올릴 수 있게 되었다.
제한사항에서 "최솟값이 8보다 크면 -1을 return 한다" 라고 하였다. 즉, N을 8번까지만 사용할 수 있는 것이다.
따라서 dp[] 리스트를 8까지만 생성하였다.
테스트 1 〉
통과 (1.22ms, 10.5MB)
테스트 2 〉
통과 (0.01ms, 10.3MB)
테스트 3 〉
통과 (0.03ms, 10.5MB)
테스트 4 〉
통과 (2210.31ms, 184MB)
테스트 5 〉
통과 (828.40ms, 70.1MB)
테스트 6 〉
통과 (0.68ms, 10.4MB)
테스트 7 〉
통과 (0.50ms, 10.6MB)
테스트 8 〉
통과 (418.25ms, 48.4MB)
테스트 9 〉
통과 (0.00ms, 10.3MB
Step 1
d = [[] for _ in range(9)]
if N == number : return 1
d[1] = [N]
d[2].extend(list(set([10*N+N, N+N, N-N, N*N, N//N])))
if number in d[2] : return 2
만약 N 이 구해야하는 number 과 같을 경우, N 1개로 만들 수 있음을 의미하므로 1을 리턴한다.
d[i]는 N을 i개 이용해서 만들 수 있는 모든 경우의 숫자를 저장해놓은 것이다.
따라서 d[1] 은 N하나만 만들 수 있고,
d[2] 는 NN과 사칙연산을 이용한 4가지 결과값이 될 것이다. 중복된 값을 피하기 위해 set() 으로 감싸준 후 다시 list() 로 변환시켰다.
만약, d[2] 에 number 가 포함되었다면 2를 리턴한다.
Step 2
for i in range(3, 9) :
d[i].extend([int(str(N) * i)])
for j in range(1, int(round(i/2))+1) :
for k in product(d[j], d[i-j]) :
t1 = k[0] + k[1]
t2 = k[0] - k[1]
t3 = k[1] - k[0]
t4 = k[0] * k[1]
if k[0] != 0 and k[1] != 0 :
t5 = k[1] // k[0]
t6 = k[0] // k[1]
else : t5 = t6 = 0
tmp = list(set([t1, t2, t3, t4, t5, t6]))
if number in tmp :
return i
else :
d[i].extend(tmp)
return -1
이제 N을 3개사용한 경우 ~ 8개사용한 경우까지 Bottom Up 방식으로 d[] 를 채워나갈 것이다.
j는 1~i의절반 까지 반복하는데, 이에 대한 설명은 dp[4] 를 구하는 예시로 생각해보자.
dp[1] 과 dp[3] 의 사칙연산값, dp[2]와 dp[2] 의 사칙연산값이 모두 다를 것이므로 이에 대해 모든 경우의 수를 고려해야 하는 것이다.
'-' 와 '/' 연산의 경우, 순서의 영향을 받으므로, 인자를 앞뒤로 바꿔서도 계산해야 한다.
(N을 1개를 사용했을 때의 모든 경우 값) + - * // (N을 3개를 사용했을 때의 모든 경우 값)
(N을 2개를 사용했을 때의 모든 경우 값) + - * // (N을 2개를 사용했을 때의 모든 경우 값)
(N을 3개를 사용했을 때의 모든 경우 값) + - * // (N을 1개를 사용했을 때의 모든 경우 값)
(N을 1개를 사용했을 때의 모든 경우 값) - // (N을 3개를 사용했을 때의 모든 경우 값)
에 대해 모든 순열을 구해야 한다.
이는 itertools 라이브러리의 product() 을 사용하여 구할 수 있다.
product을 사용하면 여러개의 리스트의 모든 조합하는 경우의 수를 구할 수 있기 때문이다.
따라서 dp[j] 와 dp[i-j] 값에 대해 사칙연산을 적용하고, 그 연산값에 number 가 포함된다면 i를 리턴한다.
댓글