반응형
https://programmers.co.kr/learn/courses/30/lessons/12914
코딩테스트 연습 - 멀리 뛰기 | 프로그래머스
효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2칸) 의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solut
programmers.co.kr
간단한 DP 문제.
아무 칸도 뛰지 않는 경우 (0칸) = 경우의 수 1개
1칸만 뛰는 경우 = 경우의 수 1개 (1칸)
2칸만 뛰는 경우 = 1칸만 뛰는 경우 + 2칸으로 뛰는 경우 (1 + 1) = 2개
3칸만 뛰는 경우 = (2칸만 뛰는 경우. 이 경우 1칸만 추가하면 된다) + (1칸만 뛰는 경우. 이 경우 남은 2칸을 '2칸 한번에 뛰기', '1칸 두 번 뛰기'로 결정할 수 있다.) 즉 1칸만 뛰는 경우 + 2칸만 뛰는 경우 = 3개.
이런 식으로 생각하면, 점화식은 아래와 같아진다.
dp[n칸을 뛰기 위한 경우의 수] = dp[n-1칸을 뛰기 위한 경우의 수] + dp[n-2칸을 뛰기 위한 경우의 수]
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] 백준 2231. 분해합 (0) | 2020.01.08 |
|---|---|
| [Python] 프로그래머스. 징검다리 (Level 4) (0) | 2020.01.07 |
| [Python] 백준 14891. 톱니바퀴 (1) | 2020.01.05 |
| [Python] 백준 17135. 캐슬 디펜스 (0) | 2020.01.04 |
| [Python] 백준 17070. 파이프 옮기기 1 (0) | 2020.01.03 |