n명이 가게를 함께 꾸리고, i번 사람의 지분은 w_i이다.
지분을 모두 더한 값을 W라고 한다.
가게는 달마다 그달의 손익 A원을 지분에 비례해서 나눈다.
A가 음수이면 손실이 난 달이고, 이때 각자의 몫은 0 이하가 되어 그만큼 돈을 내야 한다는 뜻이다.
첫 줄에 n과 달의 수 q가, 둘째 줄에 w_1부터 w_n까지가, 다음 q줄에 달마다 A가 한 줄에 하나씩 주어진다.
i번 사람의 몫은 먼저 A × w_i ÷ W를 넘지 않는 가장 큰 정수로 정한다.
예를 들어 3.5라면 3이고, −3.5라면 −4이고, 나누어떨어지면 그 값 그대로이다.
이때 i번 사람이 버린 부분은 A × w_i − 몫 × W이고, 이 값은 0 이상 W 미만의 정수이다.
이렇게 정한 몫을 모두 더하면 A보다 r원 적다(0 ≤ r < n).
남은 r원은 버린 부분이 큰 사람부터 r명에게 1원씩 더 준다.
버린 부분이 같으면 번호가 작은 사람이 먼저 받는다.
달마다 1번부터 n번까지의 마지막 몫을 빈칸 하나로 띄워 한 줄에 출력하라.
출력한 몫을 모두 더하면 언제나 A가 된다.
입력
1 ≤ n ≤ 1,000, 1 ≤ q ≤ 20, 1 ≤ w_i ≤ 1,000,000, −1,000,000,000 ≤ A ≤ 1,000,000,000. 모두 정수이고 음수는 앞에 -가 붙는다
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
정수 나눗셈이 음수에서 어느 쪽으로 가는지가 답을 갈라요. −7 ÷ 2를 Python -7 // 2는 −4(내림)로, C·C++·Java·C# -7 / 2는 −3(0 쪽으로 버림)으로 계산해요. JS·TS는 정수 나눗셈이 따로 없어 Math.floor(-7 / 2)가 −4, Math.trunc(-7 / 2)가 −3이고, 크레이콘은 수학.내림(-7 / 2)가 −4, 수학.몫(-7, 2)가 −3이에요. 내림이 필요할 때 Java는 Math.floorDiv(a, b)를 쓰고, C·C++·C#은 q = a / b; if (a % b < 0) q--;로 만들어요. 함정 하나: 0 쪽으로 버리면 손실인 달에 몫의 합이 A보다 커져요. 첫 예시의 −100은 세 명이 −33씩이면 −99라서 남은 돈이 −1이 되고, 나눠 줄 사람이 없어요. 내림이면 −34씩 −102이고 2원이 남아요. 함정 둘: 나머지도 달라요. Python -35 % 10은 5인데 C·C++·Java·C#·JS·TS·크레이콘의 -35 % 10은 −5예요. 버린 부분을 %로 구하면 0과 음수가 섞여서, 둘째 예시의 −6에서 버린 부분이 0인 1번이 가장 큰 사람으로 뽑혀요. Java Math.floorMod를 쓰거나 A × w − 몫 × W로 구해요. 함정 셋: A × w는 10^15까지 가서 C·C++·Java·C#의 int로는 넘쳐요(둘째 예시의 마지막 달). long long·long을 쓰고, C#과 Java는 넘쳐도 오류 없이 틀린 값이 돼요. JS·TS·크레이콘의 수는 2^53(약 9 × 10^15)까지 정확해서 그대로 되고, 이 범위에서는 Math.floor(a / b)도 정확해요. 함정 넷: Python에서 int(A * w / W)는 내림이 아니라 0 쪽 버림이에요(int(-3.5)는 −3). //를 써요. 함정 다섯: 버린 부분이 같으면 번호가 작은 사람이 먼저예요. 첫 예시의 100에서 1원은 1번이 받아요. Python sorted, JS·TS sort, Java의 객체 배열 Arrays.sort, C# OrderByDescending, C++ stable_sort, 크레이콘 정렬은 안정 정렬이라 버린 부분만 비교해도 입력 순서가 남지만, C qsort, C++ std::sort, C# Array.Sort는 안정 정렬이 보장되지 않아서 번호까지 비교해야 해요.
Pythonmain.py · 27 줄
import sysdef split(amount, weights, total): """amount를 weights 비율로 나눈 몫 목록. 내림으로 나누고 남은 돈은 버린 부분이 큰 사람부터 1씩 준다.""" shares = [amount * w // total for w in weights] # //는 음수에서도 내림(-7 // 2 == -4) cut = [amount * w - s * total for w, s in zip(weights, shares)] # 0 이상 total 미만 left = amount - sum(shares) order = sorted(range(len(weights)), key=lambda i: (-cut[i], i)) for i in order[:left]: shares[i] += 1 return sharesdef main(): data = sys.stdin.read().split() n, q = int(data[0]), int(data[1]) weights = [int(x) for x in data[2:2 + n]] total = sum(weights) out = [] for t in range(q): amount = int(data[2 + n + t]) out.append(" ".join(map(str, split(amount, weights, total)))) print("\n".join(out))main()
JavaScriptmain.js · 21 줄
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter((x) => x !== "").map(Number);// amount를 weights 비율로 나눈 몫 배열. 내림으로 나누고 남은 돈은 버린 부분이 큰 사람부터 1씩 준다.function split(amount, weights, total) { // Math.floor는 음수에서도 내림이다(Math.trunc는 0 쪽으로 버림). 곱은 10^15 이하라 정확하다 const shares = weights.map((w) => Math.floor((amount * w) / total)); const cut = weights.map((w, i) => amount * w - shares[i] * total); // 0 이상 total 미만 let left = amount; for (const s of shares) left -= s; const order = weights.map((_, i) => i).sort((a, b) => cut[b] - cut[a] || a - b); for (let k = 0; k < left; k++) shares[order[k]] += 1; return shares;}const n = data[0];const q = data[1];const weights = data.slice(2, 2 + n);const total = weights.reduce((a, b) => a + b, 0);const out = [];for (let t = 0; t < q; t++) out.push(split(data[2 + n + t], weights, total).join(" "));console.log(out.join("\n"));
TypeScriptmain.ts · 23 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").split(/\s+/).filter((x: string) => x !== "").map(Number);// amount를 weights 비율로 나눈 몫 배열. 내림으로 나누고 남은 돈은 버린 부분이 큰 사람부터 1씩 준다.function split(amount: number, weights: number[], total: number): number[] { // Math.floor는 음수에서도 내림이다(Math.trunc는 0 쪽으로 버림). 곱은 10^15 이하라 정확하다 const shares: number[] = weights.map((w: number) => Math.floor((amount * w) / total)); const cut: number[] = weights.map((w: number, i: number) => amount * w - shares[i] * total); // 0 이상 total 미만 let left = amount; for (const s of shares) left -= s; const order: number[] = weights.map((_: number, i: number) => i).sort((a: number, b: number) => cut[b] - cut[a] || a - b); for (let k = 0; k < left; k++) shares[order[k]] += 1; return shares;}const n: number = data[0];const q: number = data[1];const weights: number[] = data.slice(2, 2 + n);const total: number = weights.reduce((a: number, b: number) => a + b, 0);const out: string[] = [];for (let t = 0; t < q; t++) out.push(split(data[2 + n + t], weights, total).join(" "));console.log(out.join("\n"));
JavaMain.java · 46 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { // amount를 weights 비율로 나눈 몫 배열. 내림으로 나누고 남은 돈은 버린 부분이 큰 사람부터 1씩 준다. static long[] split(long amount, int[] weights, long total) { int n = weights.length; long[] shares = new long[n]; long[] cut = new long[n]; long left = amount; for (int i = 0; i < n; i++) { shares[i] = Math.floorDiv(amount * weights[i], total); // /는 0 쪽으로 버리고 floorDiv는 내림 cut[i] = Math.floorMod(amount * weights[i], total); // %는 음수가 나올 수 있고 floorMod는 0 이상 left -= shares[i]; } Integer[] order = new Integer[n]; for (int i = 0; i < n; i++) order[i] = i; Arrays.sort(order, (a, b) -> cut[a] != cut[b] ? Long.compare(cut[b], cut[a]) : Integer.compare(a, b)); for (int k = 0; k < left; k++) shares[order[k]]++; return shares; } 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()), q = Integer.parseInt(st.nextToken()); int[] weights = new int[n]; long total = 0; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) { weights[i] = Integer.parseInt(st.nextToken()); total += weights[i]; } StringBuilder out = new StringBuilder(); for (int t = 0; t < q; t++) { long amount = Long.parseLong(in.readLine().trim()); long[] shares = split(amount, weights, total); for (int i = 0; i < n; i++) out.append(i > 0 ? " " : "").append(shares[i]); out.append('\n'); } System.out.print(out); }}
C#Main.cs · 48 줄
using System;using System.Linq;using System.Text;class Program{ // C#의 /는 0 쪽으로 버리므로, 나머지가 음수이면 1을 빼서 내림으로 만든다 static long FloorDiv(long a, long b) { long quot = a / b; if (a % b < 0) quot--; return quot; } // amount를 weights 비율로 나눈 몫 배열. 내림으로 나누고 남은 돈은 버린 부분이 큰 사람부터 1씩 준다. static long[] Split(long amount, int[] weights, long total) { int n = weights.Length; var shares = new long[n]; var cut = new long[n]; long left = amount; for (int i = 0; i < n; i++) { shares[i] = FloorDiv(amount * weights[i], total); cut[i] = amount * weights[i] - shares[i] * total; // 0 이상 total 미만 left -= shares[i]; } // OrderByDescending은 안정 정렬이라 버린 부분이 같으면 번호가 작은 사람이 앞에 남는다 int[] order = Enumerable.Range(0, n).OrderByDescending(i => cut[i]).ToArray(); for (int k = 0; k < left; k++) shares[order[k]]++; return shares; } static void Main() { string[] head = Console.ReadLine().Trim().Split(' '); int n = int.Parse(head[0]), q = int.Parse(head[1]); int[] weights = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray(); long total = weights.Sum(w => (long)w); var sb = new StringBuilder(); for (int t = 0; t < q; t++) { long amount = long.Parse(Console.ReadLine().Trim()); sb.Append(string.Join(" ", Split(amount, weights, total))).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 49 줄
#include <algorithm>#include <iostream>#include <numeric>#include <vector>using namespace std;// C++의 /는 0 쪽으로 버리므로, 나머지가 음수이면 1을 빼서 내림으로 만든다long long floorDiv(long long a, long long b) { long long quot = a / b; if (a % b < 0) quot--; return quot;}// amount를 weights 비율로 나눈 몫 목록. 내림으로 나누고 남은 돈은 버린 부분이 큰 사람부터 1씩 준다.vector<long long> split(long long amount, const vector<int>& weights, long long total) { int n = (int)weights.size(); vector<long long> shares(n), cut(n); long long left = amount; for (int i = 0; i < n; i++) { shares[i] = floorDiv(amount * weights[i], total); cut[i] = amount * weights[i] - shares[i] * total; // 0 이상 total 미만 left -= shares[i]; } vector<int> order(n); iota(order.begin(), order.end(), 0); // stable_sort라서 버린 부분이 같으면 번호가 작은 사람이 앞에 남는다 stable_sort(order.begin(), order.end(), [&](int a, int b) { return cut[a] > cut[b]; }); for (int k = 0; k < left; k++) shares[order[k]]++; return shares;}int main() { int n, q; cin >> n >> q; vector<int> weights(n); long long total = 0; for (int& w : weights) { cin >> w; total += w; } for (int t = 0; t < q; t++) { long long amount; cin >> amount; vector<long long> shares = split(amount, weights, total); for (int i = 0; i < n; i++) cout << (i ? " " : "") << shares[i]; cout << "\n"; } return 0;}
Cmain.c · 48 줄
#include <stdio.h>#include <stdlib.h>#define MAXN 1000static long long cut[MAXN];/* C의 /는 0 쪽으로 버리므로, 나머지가 음수이면 1을 빼서 내림으로 만든다 */static long long floor_div(long long a, long long b) { long long quot = a / b; if (a % b < 0) quot--; return quot;}/* 버린 부분이 큰 사람이 앞, 같으면 번호가 작은 사람이 앞(qsort는 안정 정렬이 보장되지 않아 번호까지 비교한다) */static int by_cut(const void *x, const void *y) { int a = *(const int *)x, b = *(const int *)y; if (cut[a] != cut[b]) return cut[a] > cut[b] ? -1 : 1; return a - b;}int main(void) { static int weights[MAXN], order[MAXN]; static long long shares[MAXN]; int n, q; if (scanf("%d %d", &n, &q) != 2) return 0; long long total = 0; for (int i = 0; i < n; i++) { if (scanf("%d", &weights[i]) != 1) return 0; total += weights[i]; } for (int t = 0; t < q; t++) { long long amount; if (scanf("%lld", &amount) != 1) return 0; long long left = amount; for (int i = 0; i < n; i++) { shares[i] = floor_div(amount * weights[i], total); cut[i] = amount * weights[i] - shares[i] * total; /* 0 이상 total 미만 */ left -= shares[i]; order[i] = i; } qsort(order, (size_t)n, sizeof order[0], by_cut); for (int k = 0; k < left; k++) shares[order[k]]++; for (int i = 0; i < n; i++) printf(i ? " %lld" : "%lld", shares[i]); printf("\n"); } return 0;}
Craykonmain.cray · 39 줄
head = 콘솔.수들읽기();n = head[0];q = head[1];weights = 콘솔.수들읽기();total = 0;각각 (w 에서 weights){ total = total + w;}cut = 새목록(n, 0);// 버린 부분이 큰 사람이 앞. 정렬은 안정 정렬이라 같으면 번호가 작은 사람이 앞에 남는다byCut(a, b){ 돌려주기 cut[b] - cut[a];}반복 (t = 0; t < q; t++){ amount = 콘솔.줄읽기().공백제거().수로변환(); shares = []; order = []; left = amount; 반복 (i = 0; i < n; i++) { // 수학.내림은 음수에서도 내림이다(수학.몫은 0 쪽으로 버림). 곱은 10^15 이하라 정확하다 share = 수학.내림(amount * weights[i] / total); cut[i] = amount * weights[i] - share * total; // 0 이상 total 미만 left = left - share; shares.넣기(share); order.넣기(i); } order.정렬(byCut); 반복 (k = 0; k < left; k++) { shares[order[k]] = shares[order[k]] + 1; } 콘솔.쓰기(shares.잇기(" "));}