b진법 주판은 자리마다 구슬을 0개부터 b - 1개까지 올려서 수를 나타낸다.
어떤 수를 b진법 주판에 올릴 때 드는 구슬의 수는 그 수를 b진법으로 적었을 때 각 자리 숫자를 모두 더한 값이다.
예를 들어 10은 2진법으로 1010이라 구슬이 2개 들고, 10진법으로는 10이라 구슬이 1개 든다.
물음 q개가 주어진다. 물음마다 수 n과 주판 k개의 진법이 주어진다.
물음마다 n을 올릴 때 구슬이 가장 적게 드는 주판의 진법과 그 구슬 수를 출력하라.
구슬 수가 가장 적은 주판이 여럿이면 그 가운데 입력에서 가장 먼저 적힌 주판을 고른다.
수와 진법을 받아 구슬 수를 돌려주는 함수를 하나 만들고 주판마다 그 함수를 불러서 풀어 보라. 다만 채점은 출력만 보므로 함수를 만들었는지는 확인하지 못한다.
입력
첫 줄에 q가 주어진다. 다음 q줄에 물음이 한 줄에 하나씩, n, k, 그리고 진법 k개가 빈칸 하나로 나뉘어 주어진다. 1 ≤ q ≤ 1,000, 1 ≤ n ≤ 1,000,000,000,000,000 (10의 15제곱), 1 ≤ k ≤ 8, 진법은 2 이상 1,000 이하의 정수이고 같은 진법이 여러 번 적힐 수 있다
출력
물음마다 한 줄에 고른 주판의 진법과 그 구슬 수를 빈칸 하나로 띄워 출력
예시 1 · stdin
3
10 3 2 3 10
5 2 4 2
10000000000 2 7 10
stdout
10 1
4 2
10 1
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
함수를 정의하는 생김새가 언어마다 달라요. Python은 def beads(n, b):, JS는 function beads(n, b) { }, TS는 여기에 n: number와 돌려주는 타입을 적어요. Java와 C#은 클래스 안에 static int beads(long n, int b)처럼 타입을 모두 적고, C와 C++도 타입을 적어요. 크레이콘은 beads(n, b) { … 돌려주기 total; }처럼 이름과 매개변수만 적어요. 정의와 호출의 차례도 달라요. C는 부르는 곳보다 위에 함수나 함수 원형(int beads(long long n, int b);)이 있어야 해요. 없으면 gcc 14와 clang은 컴파일 오류를 내고, gcc 11은 경고만 내고 넘어가요. Python은 def가 실행되기 전에 부르면 NameError로 멈춰요. JS의 function 선언과 크레이콘의 함수는 아래에 적어도 위에서 부를 수 있지만, JS에서 const beads = (n, b) => …로 만든 함수는 그 줄보다 먼저 부르면 ReferenceError예요. 수를 매개변수로 넘기면 여덟 언어 모두 값이 복사돼서, 함수 안에서 n을 0이 될 때까지 나눠도 부른 쪽의 n은 그대로예요. 함정 하나: C++에서 매개변수를 long long& n으로 적으면 복사본이 아니라 부른 쪽의 n 그 자체예요. 첫 호출이 n을 0으로 만들어서 예시의 첫 줄이 10 1이 아니라 3 0이 돼요. 함정 둘: n은 32비트 정수에 담기지 않아요. C에서 매개변수를 int n으로 적으면 넘길 때 말없이 잘려서 예시의 셋째 줄이 10 29가 돼요. Java와 C#은 long을 int 매개변수에 넘기면 컴파일 오류로 알려 줘요. 함정 셋: 합을 담는 변수를 함수 밖에 두면 호출이 끝나도 값이 남아요. 다음 호출이 앞의 합에 이어 더해서 예시의 첫 줄이 2 2가 돼요. 함수 안에서 0으로 시작하는 변수를 새로 만들어야 해요. 함정 넷: 구슬 수가 같을 때 <=로 견주면 나중에 적힌 주판으로 바뀌어요. 예시의 둘째 줄이 4 2가 아니라 2 2가 돼요. JS·TS에는 정수 나눗셈 연산자가 없어서 풀이는 나머지를 뺀 뒤 나눠요((n - n % b) / b). Python은 //, 크레이콘은 수학.몫을 써요.
Pythonmain.py · 26 줄
import sysdef beads(n, b): """n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합)""" total = 0 while n > 0: total += n % b n //= b # 매개변수 n만 줄어든다. 부른 쪽의 수는 그대로다 return totallines = sys.stdin.read().split("\n")q = int(lines[0])out = []for line in lines[1:q + 1]: nums = list(map(int, line.split())) n, bases = nums[0], nums[2:] best_base = bases[0] best = beads(n, best_base) for b in bases[1:]: count = beads(n, b) if count < best: # 같으면 먼저 적힌 주판을 그대로 둔다 best, best_base = count, b out.append(f"{best_base} {best}")print("\n".join(out))
JavaScriptmain.js · 30 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const q = Number(lines[0]);const out = [];for (let i = 1; i <= q; i++) { const nums = lines[i].trim().split(" ").map(Number); const n = nums[0]; let bestBase = nums[2]; let best = beads(n, bestBase); // function 선언은 끌어올려져서 정의보다 먼저 부를 수 있다 for (let j = 3; j < nums.length; j++) { const count = beads(n, nums[j]); if (count < best) { // 같으면 먼저 적힌 주판을 그대로 둔다 best = count; bestBase = nums[j]; } } out.push(`${bestBase} ${best}`);}console.log(out.join("\n"));// n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합)function beads(n, b) { let total = 0; while (n > 0) { const digit = n % b; total += digit; n = (n - digit) / b; // JS의 /는 소수를 내므로 나머지를 먼저 뺀다 } return total;}
TypeScriptmain.ts · 32 줄
import { readFileSync } from "node:fs";// n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합)function beads(n: number, b: number): number { let total = 0; while (n > 0) { const digit: number = n % b; total += digit; n = (n - digit) / b; // TS의 /는 소수를 내므로 나머지를 먼저 뺀다 } return total;}const lines: string[] = readFileSync(0, "utf8").split("\n");const q: number = Number(lines[0]);const out: string[] = [];for (let i = 1; i <= q; i++) { const nums: number[] = lines[i].trim().split(" ").map(Number); const n: number = nums[0]; let bestBase: number = nums[2]; let best: number = beads(n, bestBase); for (let j = 3; j < nums.length; j++) { const count: number = beads(n, nums[j]); if (count < best) { // 같으면 먼저 적힌 주판을 그대로 둔다 best = count; bestBase = nums[j]; } } out.push(`${bestBase} ${best}`);}console.log(out.join("\n"));
JavaMain.java · 39 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { // n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합). n은 int에 담기지 않아 long이다 static int beads(long n, int b) { int total = 0; while (n > 0) { total += (int) (n % b); n /= b; } return total; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int q = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int i = 0; i < q; i++) { StringTokenizer st = new StringTokenizer(in.readLine()); long n = Long.parseLong(st.nextToken()); int k = Integer.parseInt(st.nextToken()); int bestBase = Integer.parseInt(st.nextToken()); int best = beads(n, bestBase); for (int j = 1; j < k; j++) { int b = Integer.parseInt(st.nextToken()); int count = beads(n, b); if (count < best) { // 같으면 먼저 적힌 주판을 그대로 둔다 best = count; bestBase = b; } } out.append(bestBase).append(' ').append(best).append('\n'); } System.out.print(out); }}
C#Main.cs · 42 줄
using System;using System.Text;class Program{ // n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합). n은 int에 담기지 않아 long이다 static int Beads(long n, int b) { int total = 0; while (n > 0) { total += (int)(n % b); n /= b; } return total; } static void Main() { int q = int.Parse(Console.ReadLine().Trim()); var sb = new StringBuilder(); for (int i = 0; i < q; i++) { string[] parts = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); long n = long.Parse(parts[0]); int bestBase = int.Parse(parts[2]); int best = Beads(n, bestBase); for (int j = 3; j < parts.Length; j++) { int b = int.Parse(parts[j]); int count = Beads(n, b); if (count < best) // 같으면 먼저 적힌 주판을 그대로 둔다 { best = count; bestBase = b; } } sb.Append(bestBase).Append(' ').Append(best).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 37 줄
#include <iostream>using namespace std;// n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합).// n을 값으로 받으므로 여기서 줄여도 부른 쪽의 n은 그대로다int beads(long long n, int b) { int total = 0; while (n > 0) { total += (int)(n % b); n /= b; } return total;}int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int q; cin >> q; for (int i = 0; i < q; i++) { long long n; int k, bestBase; cin >> n >> k >> bestBase; int best = beads(n, bestBase); for (int j = 1; j < k; j++) { int b; cin >> b; int count = beads(n, b); if (count < best) { // 같으면 먼저 적힌 주판을 그대로 둔다 best = count; bestBase = b; } } cout << bestBase << ' ' << best << '\n'; } return 0;}
Cmain.c · 36 줄
#include <stdio.h>/* 함수 원형: main보다 뒤에 정의하므로, 부르기 전에 생김새를 먼저 알려 준다 */int beads(long long n, int b);int main(void) { int q; scanf("%d", &q); for (int i = 0; i < q; i++) { long long n; int k, best_base; scanf("%lld %d %d", &n, &k, &best_base); int best = beads(n, best_base); for (int j = 1; j < k; j++) { int b; scanf("%d", &b); int count = beads(n, b); if (count < best) { /* 같으면 먼저 적힌 주판을 그대로 둔다 */ best = count; best_base = b; } } printf("%d %d\n", best_base, best); } return 0;}/* n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합) */int beads(long long n, int b) { int total = 0; while (n > 0) { total += (int)(n % b); n /= b; /* 값으로 받은 복사본만 줄어든다 */ } return total;}
Craykonmain.cray · 32 줄
q = 콘솔.줄읽기().수로변환();반복 (i = 0; i < q; i++){ nums = 콘솔.수들읽기(); n = nums[0]; bestBase = nums[2]; // 함수는 아래에 정의했지만 먼저 부를 수 있다 best = beads(n, bestBase); 반복 (j = 3; j < nums.개수; j++) { count = beads(n, nums[j]); // 같으면 먼저 적힌 주판을 그대로 둔다 만약 (count < best) { best = count; bestBase = nums[j]; } } 콘솔.쓰기(bestBase + " " + best);}// n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합)beads(n, b){ total = 0; 동안 (n > 0) { total += n % b; n = 수학.몫(n, b); } 돌려주기 total;}