문제
https://school.programmers.co.kr/learn/courses/30/lessons/12914
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
입출력

해설
N에 도달하는 여러 가지 방법을 1234567으로 나눈 나머지로 리턴하여라.
문제를 잘 읽어보면 한 칸에서 두 칸만 뛸 수 있다는 것이 이 문제의 KeyPoint이다.
결국 내가 1번 칸이었으면 다음으로는 2번칸, 3번칸으로만 갈 수 있다는 것이고 7번칸이면 8번칸, 9번칸으로 갈 수 있다는 것이다.
다시 말해 N칸에 도달하기 위해서는 N-1칸, N-2칸에서 올 수 있으므로 N-1칸과 N-2칸에서 오는 경우의 수를 더해주는 것이다.
그러면 DP테이블은 현재 i칸에 도달하는 경우의 수라고 정의내릴 수 있을 것이다.
그래서 다음과 같은 점화식이 만들어진다.
DP[i] = DP[i-1] + DP[i-2]
그런데 문제가 있다. 결과만 %1234567하기에는 계산하던 도중에 오버플로우가 날 경우가 있다. (파이썬은 물론 없지만..)
그렇기에 다음과 같은 점화식이 탄생하게 된다.
DP[i] = (DP[i-1] + DP[i-2]) % 1234567
이거는 모듈러 연산에 의해서 다음과 같은 사항이 참이기에 가능한 점화식이다.
(A + B) % 1234567 == ((A % 1234567) + (B % 1234567)) % 1234567
정답코드
더보기
'''
'25. 08. 15
1. N에 도달할 수 있는 방식이 여러가지가 있다.
2. 해당 가짓수를 모두 세어라
2-1. 한 칸 혹은 두 칸만 뛸 수 있음
3. 수가 커질 수 있으므로 1234567로 나눈 나머지를 리턴하여라
1칸 1
2칸 1 1
2
3칸 1 1 1
2 1
1 2
4칸 1 1 1 1
2 1 1
1 2 1
1 1 2
2 2
Dp[i] = (Dp[i - 1] + Dp[i - 2]) % MOD가 되겠다.
'''
MOD = 1234567
def solution(n):
dp = [0] * 2001
dp[0] = dp[1] = 1
for i in range(2, n + 1):
dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
return dp[n]
깃허브 : https://buly.kr/EooRE4T
'코딩테스트 > programmers' 카테고리의 다른 글
| 프로그래머스 / 구현 / 영어 끝말잇기 (0) | 2025.08.17 |
|---|---|
| 프로그래머스 / 정수론 / N개의 최소공배수 (0) | 2025.08.15 |
| 프로그래머스 / 자료구조 / 귤고르기 (0) | 2025.08.15 |
| 프로그래머스 / greedy / 구명보트 (0) | 2025.08.15 |
| 프로그래머스 / 정수론 / 점프와 순간 이동 (0) | 2025.08.12 |