[백준/Python] 25706번: 자전거 묘기

문제

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

25706번: 자전거 묘기

---

문제 요약

길이가 N미터(N칸)이고 칸마다 점프대가 존재하는 직선 자전거 도로에서 자전거를 탈 때 총 몇 개의 칸을 밟게 되는지 출력한다.

 

점프대의 높이가 N이라면 N칸 만큼 건너뛴다.

---

코드

N = int(input())

arr = list(map(int, input().split()))

dp = [1] * N
# dp[i]는 i인덱스에서 달리면 밟는 칸의 개수

for i in range(N - 1, -1, -1): # 도로의 끝과 가까운 칸부터 계산
    if i + arr[i] + 1 < N: # 인덱스를 벗어나지 않아야 한다.
        dp[i] = dp[i+arr[i]+1] + 1 # i번째 칸에서 출발해서 다음으로 밟는 칸의 dp에 1 추가

print(*dp)

---

코드 설명

1. i 인덱스에서 자전거를 타고 달려서 밟는 칸의 개수를 저장하는 메모이제이션 테이블 dp를 생성한다.

+ 움직이지 않아도 1칸을 밟은 것이므로 모두 1로 초기화한다.

 

2. 도로의 끝과 가까운 칸부터 입력 받은 배열을 거꾸로 접근한다.

 

3. 계산 과정에서 인덱스를 벗어나지 않을 때, dp[i]를 i번째 칸에서 출발해서 다음으로 밟는 칸의 dp에 1을 더한 값으로 저장한다.

+ 인덱스를 벗어나면 초기 값인 1로 저장된다.

 

4. dp를 출력한다.