{}연습장
대시보드학습스킬 경로문제모의고사라이브 코테복습데이터
문제 목록〉DP〉전망대 계단 오르기← 이전다음 →
#014 · DP쉬움경우의 수,1차원 DP

전망대 계단 오르기

문제

전망대까지 이어진 계단이 n칸 있습니다. 관람객은 땅바닥인 0번 칸에서 출발해 정확히 n번 칸에 도착해야 합니다.

한 번에 오를 수 있는 칸 수는 정해진 보폭 목록 steps 안의 값들뿐입니다. 예를 들어 steps = [1, 3]이면 한 번에 1칸 또는 3칸만 오를 수 있습니다.

여기에 더해, 보수 공사 중이라 부서진 칸 목록 broken에 들어 있는 칸은 밟을 수 없습니다. 그 칸을 딛고 쉬어 가는 것은 물론이고, 잠시 지나치는 것도 안 됩니다(뛰어넘는 것은 괜찮습니다).

전망대에 도착하는 서로 다른 방법의 수를 반환하는 solution(n, steps, broken) 함수를 작성하세요. 밟는 칸의 순서가 다르면 다른 방법으로 셉니다. 도착할 방법이 없으면 0을 반환합니다.

출발점인 0번 칸과 도착점인 n번 칸은 절대 부서지지 않습니다.

예시

n steps broken 반환값 설명
4 [1,2] [] 5 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2
4 [1,2] [2] 1 2번 칸을 피하는 길은 0→1→3→4 하나뿐
5 [1,3] [2] 2 0→1→4→5, 0→3→4→5
5 [2] [] 0 2칸씩으로는 홀수 칸에 도달 불가

제약 조건

  • 1 ≤ n ≤ 40
  • 1 ≤ steps.length ≤ 3, steps의 원소는 1 이상 3 이하의 서로 다른 정수입니다
  • broken의 원소는 1 이상 n - 1 이하의 서로 다른 정수이며, 비어 있을 수 있습니다
  • 정답은 2^53 미만임이 보장됩니다

시간 복잡도 목표: O(n × steps.length)

테스트 케이스

예시 1: 부서진 칸 없음
입력: n = 4, steps = [1,2], broken = []
출력: 5
예시 2: 2번 칸이 막힘
입력: n = 4, steps = [1,2], broken = [2]
출력: 1
예시 3: 보폭 1과 3
입력: n = 5, steps = [1,3], broken = [2]
출력: 2
예시 4: 도달 불가
입력: n = 5, steps = [2], broken = []
출력: 0
계단이 한 칸
입력: n = 1, steps = [1,2], broken = []
출력: 1
보폭 세 종류
입력: n = 3, steps = [1,2,3], broken = []
출력: 4
solution.ts
에디터 로딩 중…

▶ 실행은 기록 없이 채점만, 제출은 결과가 진행률·오답노트에 기록됩니다.