.PNG)
72 -4 도전과제 : 돌다리 건너기(Bottom-Up)
철수는 학교에 가는데 개울을 만났습니다. 개울은 N개의 돌로 다리를 만들어 놓았습니다. 철
수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다.
철수가 개울을 건너는 방법은 몇 가지일까요?
▣ 입력설명
첫째 줄은 돌의 개수인 자연수 N(3≤N≤45)이 주어집니다.
▣ 출력설명
첫 번째 줄에 개울을 건너는 방법의 수를 출력합니다.
▣ 입력예제 1
7
▣ 출력예제 1
34
<내 풀이>
def dfs(k):
if dy[k]>0:
return dy[k]
if k==1 or k==2:
return k
else :
dy[k]=dfs(k-1) +dfs(k-2)
return dy[k]
if __name__=='__main__':
n=int(input())
dy=[0]*(n+1)
s=0
dfs(n)
s+=dy[-1]+dy[-2]
print(s)<풀이>
import sys
sys.stdin = open("input.txt", 'r')
n=int(input())
dy=[0]*(n+1)
dy[1]=1
dy[2]=2
for i in range(3, n+2):
dy[i]=dy[i-1]+dy[i-2]
print(dy[n+1])
<반성점>
- 굳이 dfs방식으로 해결할 필요 없음
- 직관적으로 답 정해져있는 애는 바로 dy[1]=1 이런 식으로 정해줘도 됨
<배운 점>
(1) 내가 풀이한 것
-1:돌다리는 맨 마지막 돌에 오는 경우 (여기서 한칸만 건너면 땅)
-2:맨 마지막 돌보다 하나 전 돌까지 오는 경우 (여기서 두칸만 건너면 땅)
(2) 풀이는 '땅'에 오는 기준으로 세신것
-dy[n+1] 값으로 구하심
