방앗간에 가래떡이 n개 있고, 떡마다 길이가 정수로 주어진다.
주인은 떡을 k번 썰려고 한다.
한 번 썰 때마다 지금 있는 떡 가운데 가장 긴 떡 하나를 골라 두 도막으로 나눈다. 가장 긴 떡이 여럿이면 그 가운데 어느 것을 골라도 된다.
길이가 x인 떡은 x를 2로 나눈 몫 길이의 도막과, 나머지 길이의 도막으로 나뉜다. 그래서 x가 짝수면 두 도막의 길이가 같고, 홀수면 한 도막이 1만큼 더 길다.
두 도막은 다시 떡 더미로 돌아가서, 다음에 썰 때 다른 떡들과 똑같이 길이를 견준다.
가장 긴 떡의 길이가 1이면 더 썰 수 없으므로, 남은 횟수가 있어도 거기서 그만둔다.
썰 때마다 한 줄에, 나뉜 두 도막의 길이를 짧은 것부터 빈칸 하나로 띄워 출력하라.
마지막 줄에는 다 끝났을 때 떡의 개수와 가장 긴 떡의 길이를 빈칸 하나로 띄워 출력하라.
입력
첫 줄에 n과 k가 빈칸 하나로 나뉘어 주어진다. 둘째 줄에 떡의 길이 n개가 빈칸 하나씩으로 나뉘어 주어진다. 1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000, 길이는 1 이상 1,000 이하의 정수
출력
썬 횟수만큼의 줄에 두 도막의 길이를 짧은 것부터, 그다음 마지막 줄에 떡의 개수와 가장 긴 떡의 길이
예시 1 · stdin
3 4
7 4 1
stdout
3 4
2 2
2 2
1 2
7 2
예시 2 · stdin
2 5
2 1
stdout
1 1
3 1
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
'가장 긴 것을 꺼내고, 새 값을 다시 넣기'를 되풀이하는 일에 맞는 도구가 힙(우선순위 큐)이에요. 그런데 언어마다 먼저 나오는 쪽이 달라요. 함정 하나: Python heapq, Java PriorityQueue, C# PriorityQueue<값, 우선순위>는 가장 작은 것이 먼저 나와요. 그대로 쓰면 가장 짧은 떡을 꺼내서, 예시 1에서는 길이 1을 보고 바로 그만두어 3 1 한 줄만 나오고, 예시 2는 2 1이 돼요. Python은 -x를 넣고 꺼낼 때 다시 부호를 뒤집고, Java는 new PriorityQueue<>(Collections.reverseOrder()), C#은 Enqueue(x, -x)로 써요. C++ priority_queue<int>만 가장 큰 것이 먼저 나와서 그대로 쓰면 돼요. JS·TS·C·크레이콘에는 힙이 없어서 배열로 직접 만들어요. 부모는 (i - 1) / 2번, 두 자식은 2 * i + 1번과 2 * i + 2번이에요. 함정 둘: C++의 top()은 보기만 하고 pop()은 값을 돌려주지 않아요. pop()을 빠뜨리면 썬 떡이 더미에 그대로 남아서, 예시 1이 3 4를 네 번 출력하고 11 7로 끝나요. Python heappop, Java poll, C# Dequeue는 꺼내면서 값을 돌려줘요. 함정 셋: 두 도막을 모두 x / 2로 만들면 홀수일 때 정수 나눗셈이 버린 1만큼 떡이 사라져요. 예시 1의 첫 줄이 3 3이 돼요. 긴 도막은 x - 몫으로 구해요. JS·TS와 크레이콘의 /는 반대로 소수를 내서 3.5 3.5가 나오므로 Math.floor(x / 2), 수학.몫(x, 2)로 쓰고, Python은 //를 써요. 함정 넷: 가장 긴 떡이 1인지 묻지 않으면 길이 1짜리를 0과 1로 썰어요. 예시 2가 1 1 다음에 0 1을 네 번 출력하고 7 1로 끝나요. 이 문제는 떡이 많아야 2,000개라서 매번 목록 전체에서 가장 큰 값을 찾아도 시간 안에 끝나요. 힙은 그 한 번을 떡 개수만큼이 아니라 이 크기에서 스무 번 남짓의 견주기로 끝내 줘요. 재어 보니 떡과 횟수가 각각 200,000일 때 C로 매번 전체를 훑으면 수십 초가 넘게 걸렸고, 힙은 0.1초 안에 끝났어요.
Pythonmain.py · 21 줄
import sysimport heapqdata = sys.stdin.read().split()n, k = int(data[0]), int(data[1])# heapq는 가장 작은 값이 먼저 나온다. 가장 긴 떡이 먼저 나오도록 부호를 뒤집어 넣는다heap = [-int(x) for x in data[2:2 + n]]heapq.heapify(heap)out = []for _ in range(k): if -heap[0] == 1: # 가장 긴 떡이 1이면 더 썰 수 없다 break x = -heapq.heappop(heap) # 가장 긴 떡을 꺼낸다 a = x // 2 # 짧은 도막 b = x - a # 긴 도막: x가 홀수면 1만큼 더 길다 out.append(f"{a} {b}") heapq.heappush(heap, -a) heapq.heappush(heap, -b)out.append(f"{len(heap)} {-heap[0]}")print("\n".join(out))
JavaScriptmain.js · 52 줄
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter((s) => s !== "").map(Number);const n = data[0];const k = data[1];// JS에는 힙이 없어서 배열로 직접 만든다. heap[0]이 언제나 가장 긴 떡이다const heap = [];function push(v) { heap.push(v); let i = heap.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (heap[parent] >= heap[i]) break; [heap[i], heap[parent]] = [heap[parent], heap[i]]; i = parent; }}function pop() { const top = heap[0]; const last = heap.pop(); if (heap.length > 0) { heap[0] = last; let i = 0; while (true) { const l = 2 * i + 1; const r = l + 1; let big = i; if (l < heap.length && heap[l] > heap[big]) big = l; if (r < heap.length && heap[r] > heap[big]) big = r; if (big === i) break; [heap[i], heap[big]] = [heap[big], heap[i]]; i = big; } } return top;}for (let i = 0; i < n; i++) push(data[2 + i]);const out = [];for (let i = 0; i < k; i++) { if (heap[0] === 1) break; // 가장 긴 떡이 1이면 더 썰 수 없다 const x = pop(); // 가장 긴 떡을 꺼낸다 const a = Math.floor(x / 2); // 짧은 도막. JS의 /는 3.5 같은 소수를 내므로 내림한다 const b = x - a; // 긴 도막: x가 홀수면 1만큼 더 길다 out.push(`${a} ${b}`); push(a); push(b);}out.push(`${heap.length} ${heap[0]}`);console.log(out.join("\n"));
TypeScriptmain.ts · 54 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").split(/\s+/).filter((s: string): boolean => s !== "").map(Number);const n: number = data[0];const k: number = data[1];// TS에도 힙이 없어서 배열로 직접 만든다. heap[0]이 언제나 가장 긴 떡이다const heap: number[] = [];function push(v: number): void { heap.push(v); let i = heap.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (heap[parent] >= heap[i]) break; [heap[i], heap[parent]] = [heap[parent], heap[i]]; i = parent; }}function pop(): number { const top: number = heap[0]; const last = heap.pop() as number; if (heap.length > 0) { heap[0] = last; let i = 0; while (true) { const l = 2 * i + 1; const r = l + 1; let big = i; if (l < heap.length && heap[l] > heap[big]) big = l; if (r < heap.length && heap[r] > heap[big]) big = r; if (big === i) break; [heap[i], heap[big]] = [heap[big], heap[i]]; i = big; } } return top;}for (let i = 0; i < n; i++) push(data[2 + i]);const out: string[] = [];for (let i = 0; i < k; i++) { if (heap[0] === 1) break; // 가장 긴 떡이 1이면 더 썰 수 없다 const x: number = pop(); // 가장 긴 떡을 꺼낸다 const a: number = Math.floor(x / 2); // 짧은 도막. /는 3.5 같은 소수를 내므로 내림한다 const b: number = x - a; // 긴 도막: x가 홀수면 1만큼 더 길다 out.push(`${a} ${b}`); push(a); push(b);}out.push(`${heap.length} ${heap[0]}`);console.log(out.join("\n"));
JavaMain.java · 34 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Collections;import java.util.PriorityQueue;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 k = Integer.parseInt(st.nextToken()); // PriorityQueue는 가장 작은 값이 먼저 나온다. reverseOrder()를 넘겨 가장 긴 떡이 먼저 나오게 한다 PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder()); st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) { heap.add(Integer.parseInt(st.nextToken())); } StringBuilder out = new StringBuilder(); for (int i = 0; i < k; i++) { if (heap.peek() == 1) break; // 가장 긴 떡이 1이면 더 썰 수 없다 int x = heap.poll(); // 가장 긴 떡을 꺼낸다 int a = x / 2; // 짧은 도막 int b = x - a; // 긴 도막: x가 홀수면 1만큼 더 길다 out.append(a).append(' ').append(b).append('\n'); heap.add(a); heap.add(b); } out.append(heap.size()).append(' ').append(heap.peek()); System.out.println(out); }}
C#Main.cs · 36 줄
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { string[] first = Console.ReadLine().Trim().Split(' '); int n = int.Parse(first[0]); int k = int.Parse(first[1]); string[] parts = Console.ReadLine().Trim().Split(' '); // PriorityQueue<값, 우선순위>는 우선순위가 가장 작은 것이 먼저 나온다. // 우선순위를 -길이로 주어 가장 긴 떡이 먼저 나오게 한다 var heap = new PriorityQueue<int, int>(); for (int i = 0; i < n; i++) { int len = int.Parse(parts[i]); heap.Enqueue(len, -len); } var sb = new StringBuilder(); for (int i = 0; i < k; i++) { if (heap.Peek() == 1) break; // 가장 긴 떡이 1이면 더 썰 수 없다 int x = heap.Dequeue(); // 가장 긴 떡을 꺼낸다 int a = x / 2; // 짧은 도막 int b = x - a; // 긴 도막: x가 홀수면 1만큼 더 길다 sb.Append(a).Append(' ').Append(b).Append('\n'); heap.Enqueue(a, -a); heap.Enqueue(b, -b); } sb.Append(heap.Count).Append(' ').Append(heap.Peek()); Console.WriteLine(sb); }}
C++main.cpp · 28 줄
#include <iostream>#include <queue>using namespace std;int main() { int n, k; cin >> n >> k; // priority_queue는 다른 언어와 달리 가장 큰 값이 먼저 나온다. 그대로 쓰면 된다 priority_queue<int> heap; for (int i = 0; i < n; i++) { int len; cin >> len; heap.push(len); } for (int i = 0; i < k; i++) { if (heap.top() == 1) break; // 가장 긴 떡이 1이면 더 썰 수 없다 int x = heap.top(); // top()은 보기만 한다 heap.pop(); // 꺼내는 것은 pop()이고, 값을 돌려주지 않는다 int a = x / 2; // 짧은 도막 int b = x - a; // 긴 도막: x가 홀수면 1만큼 더 길다 cout << a << ' ' << b << '\n'; heap.push(a); heap.push(b); } cout << heap.size() << ' ' << heap.top() << '\n'; return 0;}
Cmain.c · 53 줄
#include <stdio.h>/* C에는 힙이 없어서 배열로 직접 만든다. heap[0]이 언제나 가장 긴 떡이다 */static int heap[2000]; /* 처음 1,000개 + 썰 때마다 하나씩 늘어 1,000개 */static int size = 0;static void push(int v) { int i = size++; heap[i] = v; while (i > 0) { int parent = (i - 1) / 2; if (heap[parent] >= heap[i]) break; int t = heap[i]; heap[i] = heap[parent]; heap[parent] = t; i = parent; }}static int pop(void) { int top = heap[0]; heap[0] = heap[--size]; int i = 0; for (;;) { int l = 2 * i + 1, r = l + 1, big = i; if (l < size && heap[l] > heap[big]) big = l; if (r < size && heap[r] > heap[big]) big = r; if (big == i) break; int t = heap[i]; heap[i] = heap[big]; heap[big] = t; i = big; } return top;}int main(void) { int n, k; scanf("%d %d", &n, &k); for (int i = 0; i < n; i++) { int len; scanf("%d", &len); push(len); } for (int i = 0; i < k; i++) { if (heap[0] == 1) break; /* 가장 긴 떡이 1이면 더 썰 수 없다 */ int x = pop(); /* 가장 긴 떡을 꺼낸다 */ int a = x / 2; /* 짧은 도막 */ int b = x - a; /* 긴 도막: x가 홀수면 1만큼 더 길다 */ printf("%d %d\n", a, b); push(a); push(b); } printf("%d %d\n", size, heap[0]); return 0;}
Craykonmain.cray · 77 줄
// 크레이콘에는 힙이 없어서 목록으로 직접 만든다. heap[0]이 언제나 가장 긴 떡이다첫줄 = 콘솔.수들읽기();n = 첫줄[0];k = 첫줄[1];길이들 = 콘솔.수들읽기();heap = [];힙넣기(v){ heap.넣기(v); i = heap.개수 - 1; 동안 (i > 0) { 부모 = 수학.몫(i - 1, 2); 만약 (heap[부모] >= heap[i]) { 그만; } t = heap[i]; heap[i] = heap[부모]; heap[부모] = t; i = 부모; }}힙빼기(){ top = heap[0]; heap[0] = heap[heap.개수 - 1]; heap.자리빼기(heap.개수 - 1); i = 0; 동안 (참) { l = 2 * i + 1; r = l + 1; big = i; 만약 (l < heap.개수 && heap[l] > heap[big]) { big = l; } 만약 (r < heap.개수 && heap[r] > heap[big]) { big = r; } 만약 (big == i) { 그만; } t = heap[i]; heap[i] = heap[big]; heap[big] = t; i = big; } 돌려주기 top;}각각 (len 에서 길이들){ 힙넣기(len);}out = [];반복 (i = 0; i < k; i++){ 만약 (heap[0] == 1) { 그만; } x = 힙빼기(); // 가장 긴 떡을 꺼낸다 a = 수학.몫(x, 2); // 짧은 도막. /는 3.5 같은 소수를 내므로 몫을 구한다 b = x - a; // 긴 도막: x가 홀수면 1만큼 더 길다 out.넣기(a + " " + b); 힙넣기(a); 힙넣기(b);}out.넣기(heap.개수 + " " + heap[0]);콘솔.쓰기(out.잇기("\n"));