반응형
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칸을 뛰기 위한 경우의 수]
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def solution(n): | |
| table = dict() | |
| table[0], table[1] = 1, 1 | |
| for i in range(2, n+1): | |
| table[i] = table[i-1] + table[i-2] | |
| return table[n] % 1234567 |
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [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 |