위치 0에서 출발해 양의 방향으로 a 또는 b만큼 점프해요. 위치 N에 정확히 도착하려면 최소 몇 번 점프해야 하는지 구해요. blocked[x]가 1이면 그 위치에 착지할 수 없고, 0이면 착지할 수 있어요. 금지 위치를 뛰어넘는 것은 가능해요.
int solution(vector<int> blocked, int a, int b)의 두 빈칸을 채워 주세요. N은 0100, blocked 길이는 N+1이며 모든 값은 0 또는 1이고 blocked[0]은 0이에요. a와 b는 110이며 같을 수 있어요. 도착할 수 없으면 -1, N=0이면 0을 반환해요. 반환형은 int예요.
예시 1: a = 2, b = 3, blocked = {0, 0, 0, 1, 0, 0, 0} → 3. 0→2→4→6으로 가요. 0→3→6은 위치 3에 착지할 수 없어 사용할 수 없어요.
예시 2: a = 2, b = 3, blocked = {0, 0, 0, 0, 0, 0, 0, 0} → 3. 0→2→4→7로 세 번 점프해요.
실행 입력은 N a b와 다음 줄의 N+1개 금지 상태예요. main은 매개변수 구성과 결과 출력만 담당하는 채점용 코드예요.
예시 입력
6 2 3 0 0 0 1 0 0 0
예상 결과
3
예시 입력
7 2 3 0 0 0 0 0 0 0 0
예상 결과
3
핵심 개념
dp-1d: 이전 상태의 의미를 고정하고 현재 결과를 계산해요.array-1d: 항목 번호와 상태 인덱스를 구분해요.function-design: 보조 함수의 계약과 결과 조합을 확인해요.