[알고리즘] BOJ 1890번 - 점프(python3)

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy

9 / 50

 

탐색

8 / 50

 

기초 동적 프로그래밍

7 / 50(NEW!)

---

투포인터

2 / 10

 

이분탐색

0 / 10

---

문제

https://www.acmicpc.net/problem/1890

1890번: 점프

→ solved.ac 기준 실버 1 

---

문제 해결 아이디어

힌트로 준 그림2를 보면 (0, 0) -> (2, 0)으로 가는 게 두 가지 존재한다.

→ 한 번 구한 경로를 계속 사용할 수 있다. : dp 문제

→ dp[i][j]를 (i, j)로 가는 경우의 수라고 정의한다.

출발점(0, 0)은 1이며, 이중 for문으로 주어진 게임판에 접근하면서 경우의 수를 업데이트할 수 있다.

---

구현

내 풀이

import sys
input = sys.stdin.readline

n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]

dp = [[0] * n for _ in range(n)]
dp[0][0] = 1

for i in range(n):
  for j in range(n):
    if board[i][j] == 0:
      break
    x = i + board[i][j]
    y = j + board[i][j]
    if x < n:
      dp[x][j] += dp[i][j]
    if y < n:
      dp[i][y] += dp[i][j]
      
print(dp[n-1][n-1])

---

메모

• 걸린 시간: 45분
• 처음 dp[i][j]를 더해주는 게 아니고 1을 더해주는 바람에 오래 걸림..

---

마치며

드디어 골드 4... 

약 3주만에 실버 5에서 골드 4로 승급이어서 매우 기분 좋음 ✨✨