[백준] 25706번 자전거 묘기 [Python] - 다이나믹

 

 

자전거를 타고 점프대를 지나면 그 높이만큼 칸을 건너 뛴다.
1번칸부터 N번칸 까지 자전거를 타고 출발할 때, 지나가게 되는 칸의 수를 구하는 문제

 

문제

길이가 N미터인 직선 자전거 도로가 있다. 도로는 길이가 1미터인 N개의 칸으로 구분되어 있고, 가장 왼쪽에 있는 칸부터 순서대로 1번 칸, 2번 칸, …, N번 칸이다.

도로의 각 칸에는 점프대가 설치되어 있을 수 있다. i$($1 ≤ i ≤ N$)$번 칸에 설치된 점프대의 높이를 hi라고 하자. 높이가 hi인 점프대를 밟으면 그 어떤 요인과도 관계없이 다음 hi칸 위를 비행한 뒤 그다음 칸에 착지한다. 다음 예시를 확인해 보자.

자전거를 타고 1번 칸에서 출발해 앞으로 달리면 다음과 같은 일들이 순서대로 일어난다.

1. 1번 칸에 점프대가 없으므로 2번 칸으로 주행한다.
2. 2번 칸에 높이가 1인 점프대가 있어 3번 칸 위를 비행하여 4번 칸에 착지한다.
3. 4번 칸에 높이가 2인 점프대가 있어 5, 6번 칸 위를 비행하여 7번 칸에 착지한다.
4. 7번 칸에 점프대가 없으므로 8번 칸으로 주행한다.
5. 8번 칸에 높이가 3인 점프대가 있어 9번 칸 위를 비행하여 저 멀리 나아간다. $($만일 도로가 충분히 길었다면 가상의 12번 칸에 착지하였을 것이다.$)$

시은이는 각 칸에서 자전거를 타고 출발해 앞으로 달릴 때, 도로 위 몇 개의 칸을 밟게 될지 알아보려 한다. 하지만 N개의 칸에 대해 일일이 실험해 보는 건 너무 수고스럽고 귀찮은 일이 아닌가? 다음과 같은 표를 만들고 열심히 머리를 굴리던 시은이는 깨달음을 얻었다. 오른쪽에 있는 칸의 답을 활용해 왼쪽에 있는 칸의 답을 쉽게 구할 수 있다는 것이다!

출발한 칸	답	밟는 칸
1	5	1, 2, 4, 7, 8
2	4	2, 4, 7, 8
3	4	3, 4, 7, 8
4	3	4, 7, 8
5	3	5, 7, 8
6	3	6, 7, 8
7	2	7, 8
8	1	8
9	1	9

점프대가 없는 1번 칸의 답은 바로 다음 2번 칸의 답에 1을 더한 것과 같다. 높이 1의 점프대가 있는 2번 칸의 답은 한 칸을 건너뛴 4번 칸의 답에 1을 더한 것과 같다. 다른 칸들도 같은 방식으로 답을 구할 수 있다. 특히 도로를 벗어나게 되는 8번 칸과 9번 칸의 답은 1$($각각 밟는 칸이 8번, 9번뿐이다$)$ 임을 확인하자.

여러분이 할 일은 이 놀라운 사실을 이용해 시은이의 궁금증을 해결하는 프로그램을 만드는 것이다. 이 사실을 이용하지 않으면 채점 결과로 시간초과를 받을 수 있으니 되도록이면 이용해 보자.

입력

첫번째 줄에 도로의 길이 N이 주어진다.

두번째 줄에 1번 칸부터 N번 칸까지 순서대로 각 칸에 설치된 점프대의 높이가 공백을 구분으로 주어진다. 단, 점프대가 없는 칸은 0이 주어진다.

출력

1번 칸부터 N번 칸까지 순서대로, 각 칸에서 자전거를 타고 앞으로 달리면 총 몇 개의 칸을 밟게 되는지 출력한다. 각 출력은 공백으로 구분한다.

제한

• 1 ≤ N ≤ 200,000
• 1 ≤ 점프대의 높이 ≤ 200,000

25706번: 자전거 묘기 $($acmicpc.net$)$

 

 

 

시간 초과

import sys
N = int(sys.stdin.readline())
li = list(map(int, sys.stdin.readline().split()))
steps = [0] * N
for i in range(N):
    c = 0
    for j, h in enumerate(li[i:]):
        if not c:
            steps[i] += 1
            if h:
                c += h
        else:
            c -= 1
print(*steps)

 

마지막 칸은 1번만 밟고 뒤로 갈수록 밟을 수 있는 칸의수가 증가한다.
마지막 칸부터 각 칸에서 출발하면 총 몇 칸$($=n$)$을 밟게 되는지 세면 시간 초과를 피할 수 있다.
점프대에서는 그 높이만큼 건너 뛰기 때문에

건너 뛰어서 도착한 곳에서의 n을 $n_{1}$이라고 하면 점프대에서는 $n_{1} + 1$ 칸을 밟아야 한다.

import sys
N = int(sys.stdin.readline())
li = list(map(int, sys.stdin.readline().split()))[::-1]  # 역순으로 저장

# 0으로 초기화
steps = [0]  # 정답 저장하는 리스트
current_steps = 0  # 현재 칸에서 가능한 이동 거리

# 동적 프로그래밍을 통한 최대 이동 거리 계산
for i, jump in enumerate(li):
    current_steps += 1
    if jump:
        current_steps = steps[max(i - jump, 0)] + 1
    steps.append(current_steps)
steps.pop(0)  # 초기화 때 추가한 0 값을 삭제

print(*steps[::-1])  # 역순으로 출력

 

뒤에서 부터 채우는 것만 챙각해서 리스트를 뒤집어서 했다가, 

그냥 인덱스만 뒤집으면 될 거 같아서 더 짧게 적어봤습니다.
메모리는 조금 더 쓰는데, 출력도 조금 더 빠르게 문자열로 바꿔봤습니다.

import sys
N = int(sys.stdin.readline())
li = list(map(int, sys.stdin.readline().split()))
steps, n = [0]*(N+1), 0
for i in range(N-1, -1, -1):
    steps[i] = steps[min(i+li[i]+1,N)]+1
print(" ".join(map(str,steps[:-1])))

 

예제 입력 1 

9
0 1 0 2 1 0 0 3 0

예제 출력 1 

5 4 4 3 3 3 2 1 1

예제 입력 2 

10
1 0 0 5 0 0 3 0 0 0

예제 출력 2 

4 4 3 2 3 2 1 3 2 1

예제 입력 3 

1
200000

예제 출력 3 

1