문제의 핵심
효진이는 한 번에 1칸 또는 2칸을 뛸 수 있다.
칸이 n개 있을 때 , 효진이가 끝에 도달하는 방법의 수를 구하는 것이다.
접근 방법
효진이가 끝에 도달하는 방법은 피보나치 수열과 유사하다.
- (n-1) 번째 칸에서 1칸을 뛰어 n번째 칸에 도달
- (n-2) 번째 칸에서 2칸을 뛰어 n번째 칸에 도달
따라서 ways(n) = ways(n-1) + ways(n-2) 이 된다.
코드
def solution(n):
temp = dict()
temp[0] = 1
temp[1] = 1
for i in range(2, n+1):
temp[i] = temp[i-1] + temp[i-2]
answer = temp[n] % 1234567
return answer
풀이
주어진 문제에서 'n'의 범위가 1부터 2000까지이기 때문에 , 모든 범위에 대해 효율적으로 답을 계산할 수 있는 방법이 필요하다.
만약 n=4와 같은 작은 값에 대해서만 답을 구한다고 하면 더 간단한 방법으로도 계산 가능하다.
def count_ways(n):
if n == 0:
return 1
if n == 1:
return 1
return count_ways(n-1) + count_ways(n-2)
# 테스트 예제
print(count_ways(4)) # 출력: 5
하지만, 재귀함수는 'n'이 커질 수록 계산 시간이 급격히 늘어나기 때문에 효율적이지 않다.
따라서, 효율적인 동적 프로그래밍(DP) 방식을 사용하는 것이 중요하다.
이를 통해 중복 계산을 피하고, 계산 시간을 크게 줄일 수 있다.
728x90
반응형
'코테 문제 풀기' 카테고리의 다른 글
[프로그래머스] 기능 개발 (with. 파이썬 python) (1) | 2024.07.10 |
---|---|
[프로그래머스] 예상 대진표 (.python) (0) | 2024.07.05 |
[프로그래머스] K번째 수 - with. 파이썬 (python) (0) | 2024.05.20 |
[프로그래머스] 정수 제곱근 판별 (파이썬/ python) (0) | 2024.04.03 |
[프로그래머스] 문자열 내 p와 y의 개수 (파이썬/python) (0) | 2024.04.03 |