3Level 멀리뛰기
문제 링크
< 문제 핵심 >
-
규칙성을 찾기
→ dp[0] = 1
→ dp[1] = 2
→ dp[2] = dp[0]+dp[1] = 1+2 = 3
→ dp[3] = dp[1]+dp[2] = 2+3 = 5
→ dp[n-1] = dp[n-3]+dp[n-2] = ?!
< 문제 아이디어 >
-
dp 사용
→ 2*n 타일링과 유사 ( 이 문제는 효율성 존재 )
< 코드 >
1. dp 사용
def solution(n):
dp = [1,2]
for i in range(2, n):
dp.append(dp[i - 1] + dp[i - 2])
return dp[n - 1] % 1234567
print(solution(1))
< 구현 방식 >
규칙성을 찾기
→ dp[0] = 1
→ dp[1] = 2
→ dp[2] = dp[0]+dp[1] = 1+2 = 3
→ dp[3] = dp[1]+dp[2] = 2+3 = 5
→ dp[n-1] = dp[n-3]+dp[n-2] = ?!
-
dp 사용
→ 2*n 타일링과 유사 ( 이 문제는 효율성 존재 )
< 코드 >
1. dp 사용
def solution(n):
dp = [1,2]
for i in range(2, n):
dp.append(dp[i - 1] + dp[i - 2])
return dp[n - 1] % 1234567
print(solution(1))
< 구현 방식 >
def solution(n):
dp = [1,2]
for i in range(2, n):
dp.append(dp[i - 1] + dp[i - 2])
return dp[n - 1] % 1234567
print(solution(1))
( 사용한 메소드, 라이브러리 등 원리 )
1. dp 사용
-
dp = []를 생성
-
규칙성 찾기
→ dp[0] = 1
→ dp[1] = 2
→ dp[2] = dp[0]+dp[1] = 1+2 = 3
→ dp[3] = dp[1]+dp[2] = 2+3 = 5
→ dp[n-1] = dp[n-3]+dp[n-2]
-
for문을 이용
-
0,1 부분은 이미 넣어두었기 때문에 range(2,n)으로 범위 지정
-
각 부분을 대입할수도 있지만 저는 append를 이용
→ dp.append(dp[n-3]+dp[n-2])
-
-
n == 1일 경우 예외로 설정
→ 굳이 필요없지만 쓸데없이 돌아가는 코드를 없애기 위함
-
dp[n-1] 리턴
→ 찾고자하는 n부분의 인덱스는 n-1이기 때문에
< 결과 >
1. dp 사용
Author And Source
이 문제에 관하여(3Level 멀리뛰기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hayeon/3Level-멀리뛰기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)