728x90
문제 풀이 코드만 궁금한 분은 깃허브링크 눌러주세요,,!!
문제 설명
문제 해결 논리
어차피 값들은 아랫쪽, 오른쪽으로만 진행할 수 있다. 따라서 맨 윗 행은 왼쪽 값들에만 영향을 받고 맨 왼쪽 열은 윗쪽 값들에만 영향을 받는다. 따라서 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
'코딩테스트 > 백준' 카테고리의 다른 글
백준 1495번 기타리스트 해설/코드 (파이썬) 좋은 다이나믹 프로그래밍 문제 (0) | 2021.10.11 |
---|---|
백준 15989번 1,2,3 더하기 4 해설/코드(파이썬) 다이나믹 프로그래밍 문제 (0) | 2021.10.11 |
백준 13549번 숨바꼭질3 풀이/코드 (파이썬) 우선순위 큐를 활용한 bfs문제! (0) | 2021.10.11 |
백준 12851 숨바꼭질 2 문제 풀이/해설/코드 (파이썬) 생각보다 간단한 큐, bfs 문제 (0) | 2021.10.07 |
백준 2606번 바이러스 문제 풀이/해설/코드 (파이썬) 사이클을 확인하는 문제. (0) | 2021.10.07 |