[Programmers] 경사로의 개수

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/214290

프로그래머스

 

행렬 DP 문제였습니다.

 

알고리즘은 다음과 같습니다.

1. 격자의 각 칸을 하나의 상태로 보고, d 수열 한 번의 이동을 전이로 표현합니다.

 

2. 각 상태에서 시작했을 때 경사 이동 한 번에 따른 이동 가능 경로의 수를 계산하여 전이 행렬 M를 구성합니다.

 

3. k번 연속해서 경사 이동을 수행한 후의 결과를 구합니다.

• 2번에서 구한 전이 행렬 M을 k번 제곱한 M^k

 

4. 격자 내 모든 출발 상태에서의 경로 수를 Mk 행렬의 모든 원소 합산을 통해 구하고, 결과를 모듈러 연산하여 반환합니다.

 

 

개발환경: Programmers IDE   

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~