https://school.programmers.co.kr/learn/courses/30/lessons/12914
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
계단 1칸 - 1가지
계단 2칸 - 2가지
.... 계단의 n칸?
이 무엇일까로 접근을 하였습니다.
d(n) = d(n-1) + d(n-2)로 dfs로 구현하여서 실행을 해보았습니다.
def solution(n):
# d(n) = d(n-1) + d(n-2)
def dfs(n):
if n == 1:
return 1
elif n == 2:
return 2
else:
return dfs(n-1) + dfs(n-2)
cnt = dfs(n)
return cnt실행결과
그러면 그렇지 너무 쉽다했다..ㅜ
테스트케이스 하나는 실패할 뿐더러(음..아마도 특이케이스를 잡아야한다)
더 중요한 것은 시간초과!
음..시간복잡도를 줄이는 방향으로 풀이를 해야겠습니다.
def solution(n):
if n == 1:
return 1
# dp테이블 초기화
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3,n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[-1]%1234567dfs가 아닌 dp를 사용하여서 간단하게 풀었습니다.
문제의 핵심인 수열을 생각을 하였는데 더 깊게 생각하여서 바로 풀이하지 못하였습니다.
다음엔 푼다!