개울에 돌 n개가 왼쪽부터 1번, 2번, …, n번으로 한 줄로 놓여 있다.
i번 돌에는 정수 a_i가 적혀 있다.
i번 돌에 앉은 개구리는 언제나 i + a_i번 돌로 뛴다. a_i가 음수이면 왼쪽으로, 0이면 제자리로 뛴다.
뛴 곳이 1보다 작거나 n보다 크면 개구리는 개울을 벗어난다.
개구리가 이미 앉았던 돌에 다시 내리면 같은 길을 끝없이 되풀이하므로 개울을 벗어나지 못한다. 출발한 돌도 앉았던 돌로 친다.
개구리 q마리가 차례로 따로따로 출발한다. 앞 개구리의 길은 뒤 개구리와 상관없다.
첫 줄에 n이, 둘째 줄에 a_1부터 a_n까지가, 셋째 줄에 q가, 넷째 줄에 개구리마다 출발하는 돌 번호가 빈칸으로 띄워 주어진다.
개구리마다 한 줄에, 개울을 벗어나면 벗어날 때까지 뛴 횟수를 출력하라. 벗어나는 마지막 점프도 센다.
벗어나지 못하면 -1을 출력하라.
입력
1 ≤ n ≤ 2,000, -n ≤ a_i ≤ n, 1 ≤ q ≤ 200, 1 ≤ 출발하는 돌 번호 ≤ n
출력
q줄, 줄마다 뛴 횟수 또는 -1
예시 1 · stdin
6
2 4 -2 -4 -3 1
5
1 2 4 5 6
stdout
-1
2
1
3
1
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
돌 번호는 1부터, 여덟 언어의 목록 번호는 모두 0부터라서 출발할 때 한 번 i = s - 1로 바꾸고, 그 뒤로는 목록 번호로만 생각하는 게 덜 헷갈려요. 그러면 개울 안은 0 <= i < n이에요(Python은 0 <= i < n을 그대로 쓰고, 다른 언어는 i >= 0 && i < n). 바꾸지 않고 a[s]로 시작하면 한 칸 옆 돌에서 출발하고, 끝 검사를 i < n - 1로 쓰면 n번 돌을 개울 밖으로 봐요. 범위를 먼저 묻고 나서 a[i]를 읽어야 해요. 범위 밖을 읽으면 Python은 음수 번호를 뒤에서 세어 조용히 틀리고(a[-1]은 마지막 돌), JS·TS는 undefined를 주어 i + undefined가 NaN이 돼요. Java·C#은 예외, 크레이콘은 실행 오류로 멈추고, C·C++ 배열은 아무 값이나 읽는 정해지지 않은 동작이에요. 앉았던 돌 기록은 개구리마다 새로 만들어야 해요. Python [False] * n, JS new Array(n).fill(false), Java new boolean[n], C# new bool[n](둘 다 처음부터 false), C memset(seen, 0, sizeof seen), C++ std::vector<bool>(n, false), 크레이콘 새목록(n, 거짓)이에요. 기록을 하나만 두고 계속 쓰면 앞 개구리가 밟은 돌에 내렸을 뿐인데 갇혔다고 나와요. 벗어나는 마지막 점프를 빼고 세는 것도 흔한 실수예요.
Pythonmain.py · 14 줄
n = int(input())a = list(map(int, input().split()))q = int(input())out = []for s in map(int, input().split()): seen = [False] * n # 개구리마다 새로 — 앞 개구리의 기록을 쓰면 안 된다 i = s - 1 # 돌 번호(1부터) → 목록 번호(0부터) jumps = 0 while 0 <= i < n and not seen[i]: seen[i] = True i += a[i] jumps += 1 out.append(jumps if not 0 <= i < n else -1)print("\n".join(map(str, out)))
JavaScriptmain.js · 19 줄
const tokens = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);let pos = 0;const n = tokens[pos++];const a = tokens.slice(pos, pos + n);pos += n;const q = tokens[pos++];const out = [];for (let t = 0; t < q; t++) { const seen = new Array(n).fill(false); // 개구리마다 새로 let i = tokens[pos++] - 1; // 돌 번호(1부터) → 배열 번호(0부터) let jumps = 0; while (i >= 0 && i < n && !seen[i]) { seen[i] = true; i += a[i]; jumps++; } out.push(i >= 0 && i < n ? -1 : jumps);}console.log(out.join("\n"));
TypeScriptmain.ts · 20 줄
import { readFileSync } from "node:fs";const tokens: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);let pos = 0;const n = tokens[pos++];const a: number[] = tokens.slice(pos, pos + n);pos += n;const q = tokens[pos++];const out: number[] = [];for (let t = 0; t < q; t++) { const seen: boolean[] = new Array<boolean>(n).fill(false); // 개구리마다 새로 let i = tokens[pos++] - 1; // 돌 번호(1부터) → 배열 번호(0부터) let jumps = 0; while (i >= 0 && i < n && !seen[i]) { seen[i] = true; i += a[i]; jumps++; } out.push(i >= 0 && i < n ? -1 : jumps);}console.log(out.join("\n"));
JavaMain.java · 28 줄
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine().trim()); int[] a = new int[n]; StringTokenizer st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(in.readLine().trim()); st = new StringTokenizer(in.readLine()); StringBuilder out = new StringBuilder(); for (int t = 0; t < q; t++) { boolean[] seen = new boolean[n]; // 개구리마다 새로(모두 false) int i = Integer.parseInt(st.nextToken()) - 1; // 돌 번호(1부터) → 배열 번호(0부터) int jumps = 0; while (i >= 0 && i < n && !seen[i]) { seen[i] = true; i += a[i]; jumps++; } out.append(i >= 0 && i < n ? -1 : jumps).append('\n'); } System.out.print(out); }}
C#Main.cs · 29 줄
using System;using System.Linq;using System.Text;class Program{ static void Main() { int n = int.Parse(Console.ReadLine()); int[] a = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); Console.ReadLine(); int[] starts = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); var sb = new StringBuilder(); foreach (int s in starts) { bool[] seen = new bool[n]; // 개구리마다 새로(모두 false) int i = s - 1; // 돌 번호(1부터) → 배열 번호(0부터) int jumps = 0; while (i >= 0 && i < n && !seen[i]) { seen[i] = true; i += a[i]; jumps++; } sb.Append(i >= 0 && i < n ? -1 : jumps).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 24 줄
#include <iostream>#include <vector>int main() { std::ios::sync_with_stdio(false); int n, q; std::cin >> n; std::vector<int> a(n); for (int& x : a) std::cin >> x; std::cin >> q; for (int t = 0; t < q; t++) { int s; std::cin >> s; std::vector<bool> seen(n, false); // 개구리마다 새로 int i = s - 1; // 돌 번호(1부터) → 배열 번호(0부터) int jumps = 0; while (i >= 0 && i < n && !seen[i]) { seen[i] = true; i += a[i]; jumps++; } std::cout << ((i >= 0 && i < n) ? -1 : jumps) << '\n'; }}
Cmain.c · 26 줄
#include <stdio.h>#include <string.h>int main(void) { static int a[2000]; static char seen[2000]; int n, q; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); scanf("%d", &q); for (int t = 0; t < q; t++) { int s; scanf("%d", &s); memset(seen, 0, sizeof seen); /* 개구리마다 새로 */ int i = s - 1; /* 돌 번호(1부터) → 배열 번호(0부터) */ int jumps = 0; /* 범위를 먼저 물어야 a[i]·seen[i]가 배열 밖을 읽지 않는다 */ while (i >= 0 && i < n && !seen[i]) { seen[i] = 1; i += a[i]; jumps++; } printf("%d\n", (i >= 0 && i < n) ? -1 : jumps); } return 0;}
Craykonmain.cray · 25 줄
n = 콘솔.줄읽기().수로변환();a = 콘솔.수들읽기();q = 콘솔.줄읽기().수로변환();starts = 콘솔.수들읽기();각각 (s 에서 starts){ seen = 새목록(n, 거짓); // 개구리마다 새로 i = s - 1; // 돌 번호(1부터) → 목록 번호(0부터) jumps = 0; // 범위를 먼저 물어야 seen[i]가 목록 밖을 읽지 않는다 동안 (i >= 0 && i < n && !seen[i]) { seen[i] = 참; i += a[i]; jumps += 1; } 만약 (i >= 0 && i < n) { 콘솔.쓰기(-1); } 아니면 { 콘솔.쓰기(jumps); }}