풀이
Four Fours 퍼즐과 비슷한 형태이나 사용할 수 있는 수가 N으로 주어진다. 최소 개수를 반환하라길래 얼핏 BFS로 푸는 건가 생각했으나 연산 순서 때문에 다이나믹 프로그래밍으로 풀어야 한다는 사실을 깨달았다. (문제 카테고리부터가 동적계획법이다.)
top-down으로 풀기엔 범위가 너무 넓으니 bottom-up으로 풀어야겠다는 감이 온다. 그렇다면 분할 기준을 무엇으로 삼을 것이냐? 숫자 개수의 최댓값이 8이라는 조건이 있기 때문에 이를 활용할 수 있다.
N을 하나 사용해서 만들 수 있는 수는 N뿐이다. 둘 사용해서 만들 수 있는 수는 NN, N + N, N - N, N * N, N // N이다. 이를 일반화해서 N을 k번 사용해서 만들 수 있는 수는 N을 k번 반복한 NN…NN과 (N을 i(= k 미만의 자연수)번 사용해서 만든 수)와 (N을 (k - i)번 사용해서 만든 수)를 연산한 결과들의 집합일 것이다. 만약 k가 8 이하일 때 number을 만들 수 있다면 해당 k를 반환하면 되고, 모든 가능성을 따졌을 때도 실패한다면 -1을 반환하면 된다.
코드
def solution(N, number):
# available[k] : N을 k번 사용해 만들 수 있는 수
available = [[]]
# N을 i번 사용해 만들 수 있는 수의 subset
for i in range(1, 9):
# NN...NN = N * 11...11
subset = set([N * (10**i - 1) // 9])
for j in range(1, i):
for a in available[j]:
for b in available[i - j]:
subset.add(a + b)
subset.add(a - b)
subset.add(a * b)
if b != 0:
subset.add(a / b)
if number in subset:
return i
available.append(subset)
return -1사족
레벨 3에 동적계획법을 사용하라는 사실도 친절하게 알려주는데 정답률이 26% 밖에 안 되는 문제다. 아마 분할 기준을 정하기가 까다로워서 그런 게 아닐까 짐작해 본다.
'int' object is not iterable 오류가 발생했는데 어디서 발생한 건지 감도 안 와서 VS Code에 붙여넣어서 실행해보니, set(N * (10**i - 1) // 9)에서 발생한 오류였다. set 생성자에는 iterable한 객체가 들어가야 하는데 정수형 값을 넣어서 오류가 난 것이다. 중괄호로 set 리터럴을 생성하거나 set 생성자에 전달하는 값을 리스트로 한 번 감싸주니 해결되었다. 추가로 검색해보니 생성자 함수를 호출하는 것보다 리터럴로 생성하는 것이 더 빠르다고 한다. (그런데 저걸 풀 당시에는 중괄호로 set 리터럴을 생성할 수 있는 줄 몰랐음)
