구슬 n개가 한 무더기로 쌓여 있고, 두 사람이 번갈아 구슬을 가져간다.
한 차례에 1개 이상 k개 이하를 가져가야 하고, 남은 구슬보다 많이 가져갈 수는 없다.
상대가 바로 앞 차례에 가져간 개수와 같은 개수는 가져갈 수 없다.
맨 처음 차례에는 이 제한이 없다.
자기 차례에 가져갈 수 있는 개수가 하나도 없는 사람이 진다.
구슬이 하나도 남지 않았을 때는 물론이고, 구슬이 남아 있어도 가져갈 수 있는 개수가 모두 막혀 있으면 진다. 예를 들어 상대가 방금 1개를 가져가서 1개가 남았다면 가져갈 수 없으므로 진다.
두 사람 모두 자기가 이길 방법이 있으면 반드시 그렇게 둔다.
k는 하나로 정해져 있고, n이 q개 주어진다.
n마다, 먼저 두는 사람이 첫 차례에 가져갔을 때 그 뒤로 상대가 어떻게 두어도 이길 수 있는 개수를 모두 구하라.
그런 개수를 작은 것부터 빈칸 하나로 띄워 한 줄에 출력하고, 하나도 없으면 0을 출력한다.
입력
첫 줄에 k와 q가 빈칸 하나로 나뉘어 주어지고, 다음 q줄에 줄마다 n이 하나씩 주어진다. 1 ≤ k ≤ 10, 1 ≤ q ≤ 9,000, 1 ≤ n ≤ 9,000. 모두 정수다
출력
n마다 한 줄씩, 먼저 두는 사람이 이길 수 있는 첫 차례의 개수들(작은 것부터, 빈칸 하나로 띄움) 또는 0
예시 1 · stdin
4 5
2
3
5
6
9
stdout
1 2
3
0
1 3
2 4
예시 2 · stdin
1 3
1
2
7
stdout
1
1
1
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
남은 구슬 수만으로는 이기는지 알 수 없어요. '몇 개가 막혀 있는가'까지 함께 적어야 하니 표가 2차원이에요. win[r][f]를 '구슬이 r개 남고 f개가 막혀 있을 때 지금 둘 사람이 이기는가'로 두고, r이 작은 것부터 채워요(동적 계획법). t개를 가져가면 상대는 win[r - t][t] 자리에 서니, 그 값이 거짓인 t가 막히지 않은 것 중에 하나라도 있으면 이겨요. 첫 예제의 n = 2를 보면, 2개를 다 가져가도 이기고, 1개를 가져가도 상대가 1개를 따라 할 수 없어 이겨요. 그래서 1 2예요. 함정 하나: 따라 할 수 없다는 규칙을 빼면 흔한 '(k + 1)의 배수를 남기기' 놀이가 되어 n = 2에서 2, n = 6에서 1만 나와요. 함정 둘: 막힌 사람이 지는 대신 막힌 개수를 그냥 가져가게 하면 n = 2에서 2만 나오고, 둘째 예제(k = 1)의 n = 2는 0이 돼요. 함정 셋: 남은 구슬보다 많이 가져가는 것을 막지 않으면 번호가 음수가 돼요. Python은 win[-1]이 오류 없이 맨 뒤 줄을 읽어서 n = 3에 3 4처럼 틀린 답을 내요. JS·TS는 undefined가 나와 그다음 [t]에서 TypeError로 멈추고, 크레이콘도 번호가 없다고 멈춰요. Java·C#은 예외를 던지고, C·C++은 정의되지 않은 동작이에요. 함정 넷: 표를 만드는 법이에요. Python [[False] * (k + 1)] * (top + 1)과 JS·TS new Array(top + 1).fill(new Array(k + 1).fill(false))는 같은 줄 하나를 여러 번 가리켜서, 한 칸을 고치면 모든 줄이 바뀌어요(첫 예제가 전부 1로 나와요). Python은 [[False] * (k + 1) for _ in range(top + 1)], JS·TS는 Array.from({ length: top + 1 }, () => …)로 줄마다 새로 만들어요. Java new boolean[top + 1][k + 1], C# new bool[top + 1, k + 1], C++ vector<vector<char>>(top + 1, vector<char>(k + 1)), C의 전역 2차원 배열은 처음부터 줄이 따로예요. 크레이콘 새목록(끝 + 1, 새목록(k + 1, 거짓))도 줄마다 따로 만들어 줘요. 함정 다섯: 위에서부터 재귀로 풀며 기억해 두는 방식은 n이 수천이면 재귀도 수천 겹이 돼요. Python은 기본 한도 1,000을 넘어 RecursionError로 멈추니 아래에서부터 표를 채워요. 함정 여섯: 이기는 첫 수가 없으면 빈 줄이 아니라 0을 써요.
Pythonmain.py · 26 줄
import sysdef main(): data = sys.stdin.read().split() k, q = int(data[0]), int(data[1]) asks = [int(x) for x in data[2:2 + q]] top = max(asks) # win[r][f]: 구슬이 r개 남았고 f개는 가져갈 수 없을 때(f = 0이면 제한 없음), 지금 둘 사람이 이기는가 win = [[False] * (k + 1) for _ in range(top + 1)] for r in range(1, top + 1): # good: 가져가면 상대가 지는 자리로 가는 개수들(제한은 아직 따지지 않음) good = [t for t in range(1, min(k, r) + 1) if not win[r - t][t]] row = win[r] for f in range(k + 1): row[f] = len(good) >= 2 or (len(good) == 1 and good[0] != f) out = [] for n in asks: first = [t for t in range(1, min(k, n) + 1) if not win[n - t][t]] out.append(" ".join(map(str, first)) if first else "0") print("\n".join(out))main()
JavaScriptmain.js · 31 줄
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const k = data[0], q = data[1];const asks = data.slice(2, 2 + q);const top = Math.max(...asks);// win[r][f]: 구슬이 r개 남았고 f개는 가져갈 수 없을 때(f = 0이면 제한 없음), 지금 둘 사람이 이기는가// fill(배열)은 같은 배열 하나를 모든 줄에 넣으므로, 줄마다 새로 만든다const win = Array.from({ length: top + 1 }, () => new Array(k + 1).fill(false));for (let r = 1; r <= top; r++) { // 가져가면 상대가 지는 자리로 가는 개수가 몇 가지인지, 한 가지뿐이면 그것이 무엇인지 let count = 0, only = 0; for (let t = 1; t <= k && t <= r; t++) { if (!win[r - t][t]) { count++; only = t; } } for (let f = 0; f <= k; f++) { win[r][f] = count >= 2 || (count === 1 && only !== f); }}const out = [];for (const n of asks) { const first = []; for (let t = 1; t <= k && t <= n; t++) { if (!win[n - t][t]) first.push(t); } out.push(first.length > 0 ? first.join(" ") : "0");}console.log(out.join("\n"));
TypeScriptmain.ts · 31 줄
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const k = data[0], q = data[1];const asks = data.slice(2, 2 + q);const top = Math.max(...asks);// win[r][f]: 구슬이 r개 남았고 f개는 가져갈 수 없을 때(f = 0이면 제한 없음), 지금 둘 사람이 이기는가// fill(배열)은 같은 배열 하나를 모든 줄에 넣으므로, 줄마다 새로 만든다const win: boolean[][] = Array.from({ length: top + 1 }, () => new Array(k + 1).fill(false));for (let r = 1; r <= top; r++) { // 가져가면 상대가 지는 자리로 가는 개수가 몇 가지인지, 한 가지뿐이면 그것이 무엇인지 let count = 0, only = 0; for (let t = 1; t <= k && t <= r; t++) { if (!win[r - t][t]) { count++; only = t; } } for (let f = 0; f <= k; f++) { win[r][f] = count >= 2 || (count === 1 && only !== f); }}const out: string[] = [];for (const n of asks) { const first: number[] = []; for (let t = 1; t <= k && t <= n; t++) { if (!win[n - t][t]) first.push(t); } out.push(first.length > 0 ? first.join(" ") : "0");}console.log(out.join("\n"));
JavaMain.java · 40 줄
import java.util.*;public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int k = in.nextInt(), q = in.nextInt(); int[] asks = new int[q]; int top = 0; for (int i = 0; i < q; i++) { asks[i] = in.nextInt(); top = Math.max(top, asks[i]); } // win[r][f]: 구슬이 r개 남았고 f개는 가져갈 수 없을 때(f = 0이면 제한 없음), 지금 둘 사람이 이기는가 boolean[][] win = new boolean[top + 1][k + 1]; // 모두 false로 시작한다 for (int r = 1; r <= top; r++) { // 가져가면 상대가 지는 자리로 가는 개수가 몇 가지인지, 한 가지뿐이면 그것이 무엇인지 int count = 0, only = 0; for (int t = 1; t <= k && t <= r; t++) { if (!win[r - t][t]) { count++; only = t; } } for (int f = 0; f <= k; f++) { win[r][f] = count >= 2 || (count == 1 && only != f); } } StringBuilder out = new StringBuilder(); for (int n : asks) { StringJoiner first = new StringJoiner(" "); for (int t = 1; t <= k && t <= n; t++) { if (!win[n - t][t]) first.add(String.valueOf(t)); } out.append(first.length() > 0 ? first.toString() : "0").append('\n'); } System.out.print(out); }}
C#Main.cs · 51 줄
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { string[] data = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int k = int.Parse(data[0]), q = int.Parse(data[1]); var asks = new int[q]; int top = 0; for (int i = 0; i < q; i++) { asks[i] = int.Parse(data[2 + i]); top = Math.Max(top, asks[i]); } // win[r, f]: 구슬이 r개 남았고 f개는 가져갈 수 없을 때(f = 0이면 제한 없음), 지금 둘 사람이 이기는가 var win = new bool[top + 1, k + 1]; // 네모난 2차원 배열, 모두 false로 시작한다 for (int r = 1; r <= top; r++) { // 가져가면 상대가 지는 자리로 가는 개수가 몇 가지인지, 한 가지뿐이면 그것이 무엇인지 int count = 0, only = 0; for (int t = 1; t <= k && t <= r; t++) { if (!win[r - t, t]) { count++; only = t; } } for (int f = 0; f <= k; f++) { win[r, f] = count >= 2 || (count == 1 && only != f); } } var output = new StringBuilder(); foreach (int n in asks) { var first = new List<int>(); for (int t = 1; t <= k && t <= n; t++) { if (!win[n - t, t]) first.Add(t); } output.Append(first.Count > 0 ? string.Join(" ", first) : "0").Append('\n'); } Console.Write(output); }}
C++main.cpp · 44 줄
#include <algorithm>#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int k, q; cin >> k >> q; vector<int> asks(q); for (int &n : asks) cin >> n; int top = *max_element(asks.begin(), asks.end()); // win[r][f]: 구슬이 r개 남았고 f개는 가져갈 수 없을 때(f = 0이면 제한 없음), 지금 둘 사람이 이기는가 vector<vector<char>> win(top + 1, vector<char>(k + 1, 0)); // 줄마다 따로 복사된다 for (int r = 1; r <= top; r++) { // 가져가면 상대가 지는 자리로 가는 개수가 몇 가지인지, 한 가지뿐이면 그것이 무엇인지 int count = 0, only = 0; for (int t = 1; t <= k && t <= r; t++) { if (!win[r - t][t]) { count++; only = t; } } for (int f = 0; f <= k; f++) { win[r][f] = count >= 2 || (count == 1 && only != f); } } for (int n : asks) { bool printed = false; for (int t = 1; t <= k && t <= n; t++) { if (!win[n - t][t]) { if (printed) cout << ' '; cout << t; printed = true; } } if (!printed) cout << 0; cout << '\n'; } return 0;}
Cmain.c · 47 줄
#include <stdio.h>#include <stdlib.h>#define MAX_N 9000#define MAX_K 10/* win[r][f]: 구슬이 r개 남았고 f개는 가져갈 수 없을 때(f = 0이면 제한 없음), 지금 둘 사람이 이기는가 */static char win[MAX_N + 1][MAX_K + 1]; /* 전역 배열은 모두 0으로 시작한다 */int main(void) { int k, q; if (scanf("%d %d", &k, &q) != 2) return 1; int *asks = malloc(sizeof(int) * q); int top = 0; for (int i = 0; i < q; i++) { scanf("%d", &asks[i]); if (asks[i] > top) top = asks[i]; } for (int r = 1; r <= top; r++) { /* 가져가면 상대가 지는 자리로 가는 개수가 몇 가지인지, 한 가지뿐이면 그것이 무엇인지 */ int count = 0, only = 0; for (int t = 1; t <= k && t <= r; t++) { if (!win[r - t][t]) { count++; only = t; } } for (int f = 0; f <= k; f++) { win[r][f] = count >= 2 || (count == 1 && only != f); } } for (int i = 0; i < q; i++) { int n = asks[i], printed = 0; for (int t = 1; t <= k && t <= n; t++) { if (!win[n - t][t]) { printf(printed ? " %d" : "%d", t); printed = 1; } } if (!printed) printf("0"); printf("\n"); } free(asks); return 0;}
Craykonmain.cray · 52 줄
첫줄 = 콘솔.수들읽기();k = 첫줄[0];q = 첫줄[1];묻는수 = [];끝 = 0;반복 (i = 0; i < q; i++){ n = 콘솔.줄읽기().수로변환(); 묻는수.넣기(n); 끝 = 수학.큰수(끝, n);}// 이김[r][f]: 구슬이 r개 남았고 f개는 가져갈 수 없을 때(f = 0이면 제한 없음), 지금 둘 사람이 이기는가이김 = 새목록(끝 + 1, 새목록(k + 1, 거짓));반복 (r = 1; r <= 끝; r++){ // 가져가면 상대가 지는 자리로 가는 개수가 몇 가지인지, 한 가지뿐이면 그것이 무엇인지 가짓수 = 0; 하나뿐 = 0; 반복 (t = 1; t <= k && t <= r; t++) { 만약 (!이김[r - t][t]) { 가짓수 += 1; 하나뿐 = t; } } 반복 (f = 0; f <= k; f++) { 이김[r][f] = 가짓수 >= 2 || 가짓수 == 1 && 하나뿐 != f; }}각각 (n 에서 묻는수){ 첫수 = []; 반복 (t = 1; t <= k && t <= n; t++) { 만약 (!이김[n - t][t]) { 첫수.넣기(t); } } 만약 (첫수.개수 > 0) { 콘솔.쓰기(첫수); } 아니면 { 콘솔.쓰기(0); }}