코딩테스트/백준

백준 1890번 점프 해설/코드 (파이썬) 다이나믹 프로그래밍 문제

RyanKwon 2021. 10. 11. 20:10
728x90

문제 풀이 코드만 궁금한 분은 깃허브링크 눌러주세요,,!!

 

GitHub - Rhyankwon/algorithms

Contribute to Rhyankwon/algorithms development by creating an account on GitHub.

github.com

 

 

 

문제 설명

 

문제 해결 논리

 

어차피 값들은 아랫쪽, 오른쪽으로만 진행할 수 있다. 따라서 맨 윗 행은 왼쪽 값들에만 영향을 받고 맨 왼쪽 열은 윗쪽 값들에만 영향을 받는다. 따라서 0행부터 N행까지, 왼쪽부터 오른쪽으로 차근차근 계산해나가면 우리가 원하는 답을 얻을 수 있다.

 

1. 문제에서 주어진 게임판과 똑같은 크기의 0으로만 구성된 리스트 dp를 만들고 시작부분 (0,0)을 1로 표시한다. 이건 해당 요소로 갈 수 있는 경우의 수를 뜻한다.

2. 맨 첫번째 행의 맨 왼쪽부터 게임판을 확인할건데, 위에서 만든 리스트 dp에서 0이 아닌 값(a)이 나오면(해당 격자를 i,j라고 하자) 게임판의 ( i,j)격자에 써있는 값(k)를 확인해, i,j+k 그리고 i+k, j값에 a(경우의 수)를 더한다.

3. 이렇게 하다가 게임판의 값이 0이 나오면 멈추고 dp[-1][-1]을 반환한다.

 

 

 

간단히 얘기하면, 게임판과 똑같은크기의 경우의수 리스트를 만들고 경우의 수가 1 이상인 경우만(해당 칸에 갈 수 있는 경우만) 확인하고 그 칸에서 점프해서 갈 수 있는 칸 두개에 지금 경우의 수를 더해준다.

728x90