한 번에 1칸부터 power 칸까지 오를 수 있을 때 stair 칸을 오르는 방법이 몇 가지인지 세는 문제다.
다 만들어보기
먼저 경로를 전부 만들었다.
def do(n, s=[]):
if n == 0:
ans.append(s)
return
if n < 0: return
for i in range(1, power+1):
do(n - i, s + [i])
power, stair = 3, 10
ans = []
do(stair)
남은 칸에서 1~power 칸씩 빼 나가다가 정확히 0이 되면 하나 찾은 것이다. 0보다 작아지면 버린다.
이 방식은 개수뿐 아니라 [1, 2, 3, 1, 3] 같은 경로 자체를 다 갖고 있다. 어떤 경로인지 봐야 하면 이쪽이 필요하다.
개수만 세면 되는데 경로를 다 만들고 있으니 답의 개수만큼 리스트가 쌓인다.
세기만 하기
n 칸을 오르는 방법의 수는 마지막에 몇 칸을 밟고 올라왔느냐로 갈린다. 1칸을 밟고 왔으면 그 전까지 n-1 칸을 오른 것이고, 2칸이면 n-2 칸을 오른 것이다. 그래서 앞의 power 개를 더하면 된다.
power, stair = 3, 10
li = [0] * (stair + 1)
li[0] = 1
for i in range(1, stair + 1):
if i < power:
li[i] = sum(li[:i])
else:
li[i] = sum(li[i-power:i])
li[0] = 1 은 0칸을 오르는 방법이 한 가지(아무것도 안 하기)라는 뜻이다. 이 값이 있어야 나머지가 굴러간다.
앞쪽에서 i 가 power 보다 작으면 li[i-power:i] 의 시작 인덱스가 음수가 된다. 파이썬 슬라이스에서 음수는 뒤에서부터 세는 것이라 엉뚱한 데를 가리킨다. 그래서 if 로 갈랐다.
경계를 한 줄로
갈라놓고 보니 두 갈래가 하는 일이 같았다. 시작 위치를 0 아래로 안 내려가게만 하면 된다.
for i in range(1, stair + 1):
li[i] = sum(li[max(0, i - power):i])
max(0, i - power) 하나로 if 가 사라졌다.
sum 을 매번 부르므로 한 칸마다 power 개를 다시 더한다. power 가 작으면 상관없지만 커지면 직전 값에서 하나 빼고 하나 더하는 식으로 굴리는 게 낫다.
메모이제이션은 안 끝났다
위에서 아래로 내려가는 형태도 써봤는데 완성하지 못했다.
def memo(i):
if i not in dp:
sum = 0
for j in range(1, power+1):
sum += memo(i-j)
dp[i] = sum
return dp[i]
power, stair = 3, 10
dp = {0:1}
print(dp[stair])
두 군데가 비어 있다. memo(stair) 를 부르지 않고 dp[stair] 를 바로 읽어서 값이 채워지지 않는다. 그리고 i - j 가 음수로 내려가는 걸 막는 조건이 없어서 부르더라도 끝나지 않는다.
위쪽 타뷸레이션에서 max(0, ...) 로 처리한 경계가 이쪽에서는 빠져 있는 셈이다.