import itertools
def getPool(count):
if count == 1:
return [-1, 1]
list1 = list(map(lambda x:x+count, getPool(count-1)))
list2 = list(map(lambda x:x-count, getPool(count-1)))
return list1 + list2
def getN(x):
for i in itertools.count(1):
if x in getPool(i):
return i
getN(x)에 x 넣으면 되요
x에 4넣으니까 3나오네요
- 1 + 2 + 3에서 걸렸겠죠?
공간복잡도..
저는 그런 것은 모릅니다.....................
x에 10억 넣어보셈 - dc App
-3646397 넣으면 2701 나오는데.. 아조시 무덤갈때 나와양
10억은 커녕 매우 낮은 수에서 제 컴이 멈추겠죠 ㅋㅋ
자 이제 디피로 풀어봐
저건 DP 아닌데... - dc App
getPool()이 캐시안됐잖아.. 그리고 원글 덧글좀봐
디피써야함?
첨부터 다시도는구나
아녀.. 못돌아영
http://ideone.com/SNwFCK
메모지에이션도 없는 단순 재귀함수인데요 - dc App
오..
이건 덧셈정의와 등차수열합산법에서 출발해야 할 문제인데...
ㄴ 예? - dc App
저는 디피도 메모지에이션도 모릅니다.. 근데 캐시가 안 됐다는 말은 어떤 의미인가요?
+- 랑 -+ 가 규칙성이 있단 말인데유.
당연히 -1이고 +1 이되쥬.
캐시가 안됐다는건, getPool()은 인자 하나로 값이 결정되는데, 인자가 똑같은 함수를 두번 실행하면 실제로 계산도 두번 하는게 문제란 뜻이야.. 한번 계산한 애에 대해서는 리스트나 딕셔너리에 값을 저장해두면 바로 리턴할수 있자나..
A[n] = getPool(n) 이런 식으로 값을 저장해뒀다가 사용하는 거 - dc App
아하..... 뭔말인지 알겠다.
같은연산을 반복안하게 하는
물론 이 문제는 캐싱해도 답없음 - dc App
되요->돼요 (되어 = 돼임) [리듬 맞춤법 봇♬]