가로로 긴 종이 띠가 n칸으로 나뉘어 있고, 칸에는 왼쪽부터 1, 2, …, n이 적혀 있다.
띠를 접으면 여러 칸이 한 자리에 겹쳐 쌓인다. 띠의 길이는 자리의 수이고, 처음에는 자리마다 칸이 하나씩 있어 길이가 n이다.
접기 k는 왼쪽에서 k번째 자리와 k + 1번째 자리 사이를 접는 선으로 삼아, 왼쪽 k자리를 통째로 들어 오른쪽으로 뒤집어 덮는 것이다.
그러면 접는 선에서 왼쪽으로 d번째이던 자리가 접는 선에서 오른쪽으로 d번째인 자리 위에 얹힌다. 뒤집혀서 얹히므로, 넘어온 자리에 쌓여 있던 칸들은 위아래 차례가 거꾸로 된 채 받치는 자리의 칸들 위에 놓인다.
오른쪽에 받쳐 줄 자리가 없으면, 넘어온 칸들만으로 그 자리가 된다.
접은 뒤에는 접는 선 바로 오른쪽 자리가 새 1번째 자리이다. 접기 전 길이가 L이면 접은 뒤 길이는 k와 L - k 가운데 큰 값이다.
예를 들어 n = 5인 띠를 k = 2로 접으면 길이는 3이고, 자리마다 아래부터 3 2, 4 1, 5가 쌓여 있다.
접기 q번을 주어진 차례대로 한 뒤 띠의 모습을 출력하라.
입력
첫 줄에 n과 q가 빈칸 하나로 나뉘어 주어진다. 둘째 줄에 접기의 k가 q개, 접는 차례대로 빈칸 하나로 나뉘어 주어진다. 2 ≤ n ≤ 1,000, 1 ≤ q ≤ n - 1. 각 k는 1 이상이고 그때의 띠 길이보다 작다
출력
첫 줄에 마지막 띠의 길이를 출력한다. 이어서 왼쪽 자리부터 한 줄에 한 자리씩, 그 자리에 쌓인 칸의 수를 맨 아래 칸부터 맨 위 칸까지 빈칸 하나로 띄워 출력한다
예시 1 · stdin
5 2
2 2
stdout
2
5 1 4
2 3
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
한 번 접을 때 뒤집기가 두 겹으로 일어나요. 넘어가는 자리들의 차례가 뒤집히고, 자리마다 쌓인 칸의 위아래도 뒤집혀요. 뒤집는 도구가 새 목록을 주는지, 원본을 제자리에서 바꾸는지가 언어마다 달라요. Python의 s[::-1]은 새 목록을 주고, s.reverse()는 제자리에서 뒤집고 None을 돌려줘요. reversed(s)는 목록이 아니라 반복자를 줘서 목록에 +로 이으면 TypeError예요. JS·TS의 reverse()는 제자리에서 뒤집고 같은 배열을 돌려줘서, 풀이는 slice()나 [...a]로 복사한 것을 뒤집어요(toReversed()는 새 배열을 줘요). Java의 Collections.reverse, C#의 List.Reverse(), C++의 std::reverse, 크레이콘의 뒤집기()는 모두 제자리에서 뒤집고 값을 돌려주지 않아요. 그래서 넘어가는 쪽을 먼저 복사해요. Java는 new ArrayList<>(strip.subList(0, k))(subList만 쓰면 원본을 들여다보는 창이라 원본이 뒤집혀요), C#은 GetRange, 크레이콘은 부분목록이에요. C++은 rbegin()·rend()로 복사 없이 뒤에서부터 읽을 수도 있어요. C에는 목록이 없어서 모든 칸을 한 배열에 이어 적고, 넘어온 자리는 뒤에서부터 읽어 새 배열에 옮겨 적어요. 함정 하나: JS에서 strip.reverse().slice(L - k)로 넘어가는 쪽을 얻으면 strip 자체가 뒤집혀요. 그 뒤에 strip.slice(k)로 얻는 오른쪽이 엉뚱한 자리가 되어 예시의 첫 줄이 5 1 4가 아니라 3 2 1 2가 돼요. 함정 둘: 자리의 차례만 뒤집고 자리 안의 위아래를 뒤집지 않으면 예시가 5 4 1과 3 2가 돼요. 칸이 하나뿐인 첫 접기에서는 드러나지 않고 둘째 접기에서 틀려요. 함정 셋: Python에서 stack + left[d].reverse()라고 쓰면 None을 이으려는 것이라 TypeError로 멈춰요.
Pythonmain.py · 22 줄
import syslines = sys.stdin.read().split("\n")n, q = map(int, lines[0].split())folds = list(map(int, lines[1].split()))strip = [[i] for i in range(1, n + 1)] # 자리마다 쌓인 칸들(아래 → 위)for k in folds: length = len(strip) left = strip[:k][::-1] # 넘어가는 쪽: 접는 선에 가까운 자리부터 (새 목록) right = strip[k:] folded = [] for d in range(max(k, length - k)): stack = right[d] if d < length - k else [] if d < k: stack = stack + left[d][::-1] # 뒤집혀 얹히므로 위아래 차례도 거꾸로 folded.append(stack) strip = foldedout = [str(len(strip))]out += [" ".join(map(str, stack)) for stack in strip]print("\n".join(out))
JavaScriptmain.js · 23 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n] = lines[0].trim().split(" ").map(Number);const folds = lines[1].trim().split(" ").map(Number);let strip = []; // 자리마다 쌓인 칸들(아래 → 위)for (let i = 1; i <= n; i++) strip.push([i]);for (const k of folds) { const length = strip.length; // reverse()는 제자리에서 뒤집으므로, slice()로 떼어 낸 복사본을 뒤집는다 const left = strip.slice(0, k).reverse(); const right = strip.slice(k); const folded = []; for (let d = 0; d < Math.max(k, length - k); d++) { let stack = d < length - k ? right[d] : []; if (d < k) stack = stack.concat([...left[d]].reverse()); // 위아래 차례도 거꾸로 folded.push(stack); } strip = folded;}const out = [String(strip.length)];for (const stack of strip) out.push(stack.join(" "));console.log(out.join("\n"));
TypeScriptmain.ts · 25 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n]: number[] = lines[0].trim().split(" ").map(Number);const folds: number[] = lines[1].trim().split(" ").map(Number);let strip: number[][] = []; // 자리마다 쌓인 칸들(아래 → 위)for (let i = 1; i <= n; i++) strip.push([i]);for (const k of folds) { const length: number = strip.length; // reverse()는 제자리에서 뒤집으므로, slice()로 떼어 낸 복사본을 뒤집는다 const left: number[][] = strip.slice(0, k).reverse(); const right: number[][] = strip.slice(k); const folded: number[][] = []; for (let d = 0; d < Math.max(k, length - k); d++) { let stack: number[] = d < length - k ? right[d] : []; if (d < k) stack = stack.concat([...left[d]].reverse()); // 위아래 차례도 거꾸로 folded.push(stack); } strip = folded;}const out: string[] = [String(strip.length)];for (const stack of strip) out.push(stack.join(" "));console.log(out.join("\n"));
JavaMain.java · 53 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Collections;import java.util.List;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); st = new StringTokenizer(in.readLine()); List<List<Integer>> strip = new ArrayList<>(); // 자리마다 쌓인 칸들(아래 → 위) for (int i = 1; i <= n; i++) { List<Integer> one = new ArrayList<>(); one.add(i); strip.add(one); } for (int f = 0; f < q; f++) { int k = Integer.parseInt(st.nextToken()); int length = strip.size(); // subList는 원본을 들여다보는 창이라, 새 목록으로 복사한 뒤에 뒤집는다 List<List<Integer>> left = new ArrayList<>(strip.subList(0, k)); Collections.reverse(left); List<List<Integer>> folded = new ArrayList<>(); for (int d = 0; d < Math.max(k, length - k); d++) { List<Integer> stack = d < length - k ? strip.get(k + d) : new ArrayList<>(); if (d < k) { List<Integer> top = left.get(d); Collections.reverse(top); // 위아래 차례도 거꾸로 stack.addAll(top); } folded.add(stack); } strip = folded; } StringBuilder out = new StringBuilder(); out.append(strip.size()).append('\n'); for (List<Integer> stack : strip) { for (int i = 0; i < stack.size(); i++) { if (i > 0) out.append(' '); out.append(stack.get(i)); } out.append('\n'); } System.out.print(out); }}
C#Main.cs · 42 줄
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(first[0]); string[] folds = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); var strip = new List<List<int>>(); // 자리마다 쌓인 칸들(아래 → 위) for (int i = 1; i <= n; i++) strip.Add(new List<int> { i }); foreach (string token in folds) { int k = int.Parse(token); int length = strip.Count; // GetRange는 새 목록을 주고, Reverse()는 그 목록을 제자리에서 뒤집는다 List<List<int>> left = strip.GetRange(0, k); left.Reverse(); var folded = new List<List<int>>(); for (int d = 0; d < Math.Max(k, length - k); d++) { List<int> stack = d < length - k ? strip[k + d] : new List<int>(); if (d < k) { List<int> top = left[d]; top.Reverse(); // 위아래 차례도 거꾸로 stack.AddRange(top); } folded.Add(stack); } strip = folded; } var sb = new StringBuilder(); sb.Append(strip.Count).Append('\n'); foreach (List<int> stack in strip) sb.Append(string.Join(" ", stack)).Append('\n'); Console.Write(sb); }}
C++main.cpp · 36 줄
#include <algorithm>#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; vector<vector<int>> strip(n); // 자리마다 쌓인 칸들(아래 → 위) for (int i = 0; i < n; i++) strip[i].push_back(i + 1); for (int f = 0; f < q; f++) { int k; cin >> k; int length = (int)strip.size(); // 넘어가는 쪽을 복사한 뒤 std::reverse로 제자리에서 뒤집는다 vector<vector<int>> left(strip.begin(), strip.begin() + k); reverse(left.begin(), left.end()); vector<vector<int>> folded; for (int d = 0; d < max(k, length - k); d++) { vector<int> stack; if (d < length - k) stack = strip[k + d]; // rbegin/rend: 복사하지 않고 뒤에서부터 읽는다 (위아래 차례도 거꾸로) if (d < k) stack.insert(stack.end(), left[d].rbegin(), left[d].rend()); folded.push_back(stack); } strip = folded; } cout << strip.size() << '\n'; for (const auto &stack : strip) { for (size_t i = 0; i < stack.size(); i++) cout << (i ? " " : "") << stack[i]; cout << '\n'; } return 0;}
Cmain.c · 46 줄
#include <stdio.h>#define MAXN 1000/* 모든 칸을 한 배열에 자리 차례로 이어 적고, start[p]에 p번 자리의 칸이 시작하는 곳을 둔다. 접을 때마다 다른 배열에 새로 적고 두 배열을 번갈아 쓴다. */static int cells[2][MAXN];static int start[2][MAXN + 1];int main(void) { int n, q; scanf("%d %d", &n, &q); int cur = 0, length = n; for (int i = 0; i < n; i++) { cells[0][i] = i + 1; start[0][i] = i; } start[0][n] = n; for (int f = 0; f < q; f++) { int k; scanf("%d", &k); int nxt = 1 - cur; int newLength = k > length - k ? k : length - k; int w = 0; for (int d = 0; d < newLength; d++) { start[nxt][d] = w; if (d < length - k) { /* 그대로 있는 쪽: 차례대로 옮겨 적는다 */ for (int i = start[cur][k + d]; i < start[cur][k + d + 1]; i++) cells[nxt][w++] = cells[cur][i]; } if (d < k) { /* 넘어온 쪽: 뒤에서부터 읽어 거꾸로 얹는다 */ for (int i = start[cur][k - d] - 1; i >= start[cur][k - 1 - d]; i--) cells[nxt][w++] = cells[cur][i]; } } start[nxt][newLength] = w; cur = nxt; length = newLength; } printf("%d\n", length); for (int p = 0; p < length; p++) { for (int i = start[cur][p]; i < start[cur][p + 1]; i++) { printf(i > start[cur][p] ? " %d" : "%d", cells[cur][i]); } printf("\n"); } return 0;}
Craykonmain.cray · 43 줄
첫줄 = 콘솔.수들읽기();n = 첫줄[0];folds = 콘솔.수들읽기();// 자리마다 쌓인 칸들(아래 → 위)strip = [];반복 (i = 1; i <= n; i++){ strip.넣기([i]);}각각 (k 에서 folds){ length = strip.개수; // 부분목록은 새 목록을 주고, 뒤집기는 그 목록을 제자리에서 뒤집는다 left = strip.부분목록(0, k); left.뒤집기(); folded = []; 반복 (d = 0; d < 수학.큰수(k, length - k); d++) { stack = []; 만약 (d < length - k) { stack = strip[k + d]; } 만약 (d < k) { // 위아래 차례도 거꾸로 top = left[d]; top.뒤집기(); 각각 (v 에서 top) { stack.넣기(v); } } folded.넣기(stack); } strip = folded;}콘솔.쓰기(strip.개수);각각 (stack 에서 strip){ 콘솔.쓰기(stack);}