[백준 25706 - Node.js] 자전거 묘기

🔗 문제 링크

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

25706번: 자전거 묘기

✏️ 풀이

const [[N], heights] = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n')
  .map(v => v.split(' ').map(Number));

const dp = Array(N + 1).fill(0);

for (let i = N; i > 0; i--) {
  dp[i] = (dp[i + heights[i - 1] + 1] ?? 0) + 1;
}

console.log(dp.slice(1).join(' '));

제일 오른쪽 칸부터 역순으로 밟게 되는 칸 수를 구한다.현재 칸은 무조건 밟기 때문에 최소 1칸은 반드시 밟게 되고, 그 이후에는 다음 칸에서 밟게 되는 칸 수를 더하면 현재 칸에서 시작했을 때 밟게 되는 칸 수를 구할 수 있다. 그런데 "다음 칸"이 바로 뒷 칸을 의미하는 것은 아니다. 시작하는 칸이 점프대라면 (점프대의 높이 + 1) 만큼 뒤의 칸을 밟게 되고, 일반 칸이라면 바로 뒷 칸을 밟게 된다.

 

따라서 모든 칸에서 현재 칸을 밟고 그 뒤에 (점프대의 높이 + 1) 만큼 뒤의 칸을 밟게 되므로 dp[i] = dp[i + (현재 칸의 높이) + 1] + 1이 성립한다. 이 때, (점프대의 높이 + 1) 만큼의 뒤의 칸이 없을 수도 있으므로 N의 범위를 벗어나는 경우에는 0으로 계산하였다.