문제 바로가기
문제:
길이가 N미터인 직선 자전거 도로가 있다. 도로는 길이가 1미터인 N개의 칸으로 구분되어 있고, 가장 왼쪽에 있는 칸부터 순서대로 1번 칸, 2번 칸, …, N번 칸이다.
도로의 각 칸에는 점프대가 설치되어 있을 수 있다. i(1 ≤ i ≤ N)번 칸에 설치된 점프대의 높이를 hi라고 하자. 높이가 hi인 점프대를 밟으면 그 어떤 요인과도 관계없이 다음 hi칸 위를 비행한 뒤 그다음 칸에 착지한다. 다음 예시를 확인해 보자.
자전거를 타고 1번 칸에서 출발해 앞으로 달리면 다음과 같은 일들이 순서대로 일어난다.
- 1번 칸에 점프대가 없으므로 2번 칸으로 주행한다.
- 2번 칸에 높이가 1인 점프대가 있어 3번 칸 위를 비행하여 4번 칸에 착지한다.
- 4번 칸에 높이가 2인 점프대가 있어 5, 6번 칸 위를 비행하여 7번 칸에 착지한다.
- 7번 칸에 점프대가 없으므로 8번 칸으로 주행한다.
- 8번 칸에 높이가 3인 점프대가 있어 9번 칸 위를 비행하여 저 멀리 나아간다.
(만일 도로가 충분히 길었다면 가상의 12번 칸에 착지하였을 것이다.) 시은이는 각 칸에서 자전거를 타고 출발해 앞으로 달릴 때, 도로 위 몇 개의 칸을 밟게 될지 알아보려 한다. 하지만 N개의 칸에 대해 일일이 실험해 보는 건 너무 수고스럽고 귀찮은 일이 아닌가? 다음과 같은 표를 만들고 열심히 머리를 굴리던 시은이는 깨달음을 얻었다. 오른쪽에 있는 칸의 답을 활용해 왼쪽에 있는 칸의 답을 쉽게 구할 수 있다는 것이다!
점프대가 없는 1번 칸의 답은 바로 다음 2번 칸의 답에 1을 더한 것과 같다. 높이 1의 점프대가 있는 2번 칸의 답은 한 칸을 건너뛴 4번 칸의 답에 1을 더한 것과 같다. 다른 칸들도 같은 방식으로 답을 구할 수 있다. 특히 도로를 벗어나게 되는 8번 칸과 9번 칸의 답은 1(각각 밟는 칸이 8번, 9번뿐이다) 임을 확인하자.
여러분이 할 일은 이 놀라운 사실을 이용해 시은이의 궁금증을 해결하는 프로그램을 만드는 것이다. 이 사실을 이용하지 않으면 채점 결과로 시간초과를 받을 수 있으니 되도록이면 이용해 보자.
입력:
첫번째 줄에 도로의 길이 N이 주어진다. 두번째 줄에 1번 칸부터 N번 칸까지 순서대로 각 칸에 설치된 점프대의 높이가 공백을 구분으로 주어진다. 단, 점프대가 없는 칸은 0이 주어진다.
출력:
1번 칸부터 N번 칸까지 순서대로, 각 칸에서 자전거를 타고 앞으로 달리면 총 몇 개의 칸을 밟게 되는지 출력한다. 각 출력은 공백으로 구분한다.
풀이:
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n = int(input())
lst = list(map(int,sys.stdin.readline().split(" ")))
dp =[1] *(n)
for i in range(n-1,-1,-1):
# 점프 범위 조건
if i + lst[i] +1 < n:
# 최댓값 업데이트
dp[i] = dp[i + lst[i] +1]+ 1
print(*dp)
내가 생각한 방법은 dp이다.
최댓값을 업데이트 해야하기 때문이다. 하지만 범위를 앞에서부터가 아닌 거꾸로 한다.
왜냐하면 자전거가 점프하기 때문이라고 생각했다.
9
0 1 0 2 1 0 0 3 0
현재 칸은 무조건 밟게되고 점프하는 순간 그 뒤에 나오는 n칸을 못 밟는다는 뜻이다.
즉 현재 위치에서 점프 했을때 범위 안에 들어오면 그 범위 값을 더해주면 되고,
범위를 넘어가면 점프로 넘어가서 상관이 없어 고려하지 않는다.
댓글