오래된 기계식 계수기에 바퀴 n개가 한 줄로 붙어 있다.
왼쪽에서 i번째 바퀴에는 0부터 b_i - 1까지의 칸이 있고, 지금 d_i 칸을 가리킨다.
계수기를 앞으로 한 칸 돌리면 맨 오른쪽 바퀴가 1 늘어난다.
어떤 바퀴가 b_i - 1에서 한 칸 더 가면 0으로 돌아가고, 그 왼쪽 바퀴가 1 늘어난다.
맨 왼쪽 바퀴가 b_1 - 1에서 0으로 돌아가면 계수기 전체가 앞으로 한 번 넘어간 것이다.
뒤로 한 칸 돌리면 거꾸로 움직인다: 맨 오른쪽 바퀴가 1 줄고, 0에서 한 칸 더 가면 b_i - 1이 되며 그 왼쪽 바퀴가 1 준다.
맨 왼쪽 바퀴가 0에서 b_1 - 1이 되면 계수기 전체가 뒤로 한 번 넘어간 것이다.
t가 양수면 앞으로 t칸, 음수면 뒤로 -t칸 돌리고, 0이면 돌리지 않는다.
첫 줄에 n, 둘째 줄에 b_1 … b_n, 셋째 줄에 d_1 … d_n, 넷째 줄에 t가 주어진다.
같은 줄의 수는 빈칸 하나로 띄워 있다.
첫째 줄에는 다 돌린 뒤 바퀴들이 가리키는 칸을 왼쪽 바퀴부터 빈칸 하나씩 띄워 출력하라.
둘째 줄에는 계수기 전체가 넘어간 횟수를 출력하라. 앞으로 넘어갔으면 그 횟수를, 뒤로 넘어갔으면 그 횟수에 -를 붙여 쓰고, 넘어가지 않았으면 0을 쓴다.
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
맨 오른쪽 바퀴부터, 들어온 값 s = d + (넘겨받은 값)을 칸 s mod b와 왼쪽으로 넘길 몫으로 나누면 돼요. 뒤로 돌릴 때는 s가 음수라서 언어마다 %와 /가 달라요. Python의 %·//는 내림 나눗셈이라 칸이 늘 0 ~ b-1이고 몫도 아래로 내린 값(-4 // 3 == -2)이라 그대로 맞아요. C·C++·Java·C#·JS·TS·크레이콘의 %는 나누어지는 수의 부호를 따르고(-4 % 3 == -1), C·C++·Java·C#의 정수 /와 JS·TS Math.trunc(s / b), 크레이콘 수학.몫은 0 쪽으로 버려서(-4 / 3 == -1) 칸이 음수가 되고 빌림이 하나 모자라요. JS·TS·크레이콘의 /는 소수까지 나누니(-4 / 3 == -1.333…) 그대로 몫으로 쓸 수 없어요. (s % b + b) % b로 칸을 고친 다음 몫은 (s - 칸) / b로 구하거나(딱 나누어떨어져요), Java는 Math.floorMod·Math.floorDiv를 써요. 칸만 고치고 몫은 0 쪽으로 버린 나눗셈으로 두는 것도 흔한 실수예요. 둘째 함정은 크기예요. t는 10^12까지라 C·C++ long long, Java·C# long이 필요하고, int에 담으면 넘쳐요. JS·TS·크레이콘의 수는 2^53(약 9×10^15)까지 정확해서 t는 괜찮아요. 그런데 계수기 전체를 수 하나로 바꿔 계산하면 바퀴 칸 수의 곱이 60^10(약 6×10^17)까지 커져 2^53을 넘으니, 아래 자리가 틀어져요. 바퀴마다 나머지와 몫으로 넘기면 어느 언어에서도 값이 t 근처에 머물러요. Python int(s / b)도 실수 나눗셈 뒤 0 쪽으로 버리니 같은 함정이에요.
Pythonmain.py · 14 줄
n = int(input())b = list(map(int, input().split()))d = list(map(int, input().split()))t = int(input())# 오른쪽 바퀴부터: 이 바퀴에 들어온 값 s를 칸(나머지)과 왼쪽으로 넘길 값(몫)으로 나눈다# Python의 %와 //는 내림 나눗셈이라 s가 음수여도 칸은 0 ~ b-1, 몫은 아래로 내린 값이다carry = tfor i in range(n - 1, -1, -1): s = d[i] + carry d[i] = s % b[i] carry = s // b[i]print(*d)print(carry) # 맨 왼쪽 바퀴에서도 넘친 값 = 계수기 전체가 넘어간 횟수
JavaScriptmain.js · 13 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);const b = lines[1].trim().split(/\s+/).map(Number);const d = lines[2].trim().split(/\s+/).map(Number);let carry = Number(lines[3]); // 10^12는 2^53 안이라 Number로 정확하다// JS의 %는 나누어지는 수의 부호를 따른다(-7 % 3 === -1) → b를 더해 다시 나눈다for (let i = n - 1; i >= 0; i--) { const s = d[i] + carry; d[i] = ((s % b[i]) + b[i]) % b[i]; carry = (s - d[i]) / b[i]; // s - 칸은 b로 딱 나누어떨어진다: 내림 몫}console.log(d.join(" ") + "\n" + carry);
TypeScriptmain.ts · 14 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const n: number = Number(lines[0]);const b: number[] = lines[1].trim().split(/\s+/).map(Number);const d: number[] = lines[2].trim().split(/\s+/).map(Number);let carry: number = Number(lines[3]); // 10^12는 2^53 안이라 number로 정확하다// TS(JS)의 %는 나누어지는 수의 부호를 따른다(-7 % 3 === -1) → b를 더해 다시 나눈다for (let i = n - 1; i >= 0; i--) { const s: number = d[i] + carry; d[i] = ((s % b[i]) + b[i]) % b[i]; carry = (s - d[i]) / b[i]; // s - 칸은 b로 딱 나누어떨어진다: 내림 몫}console.log(d.join(" ") + "\n" + carry);
JavaMain.java · 24 줄
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] b = new int[n]; long[] d = new long[n]; for (int i = 0; i < n; i++) b[i] = sc.nextInt(); for (int i = 0; i < n; i++) d[i] = sc.nextLong(); long carry = sc.nextLong(); // 10^12: int로는 넘친다 // Java의 %와 /는 0 쪽으로 버린다(-7 % 3 == -1) → Math.floorMod·floorDiv는 내림으로 나눈다 for (int i = n - 1; i >= 0; i--) { long s = d[i] + carry; d[i] = Math.floorMod(s, (long) b[i]); carry = Math.floorDiv(s, (long) b[i]); } StringBuilder out = new StringBuilder(); for (int i = 0; i < n; i++) out.append(i > 0 ? " " : "").append(d[i]); out.append('\n').append(carry).append('\n'); System.out.print(out); }}
C#Main.cs · 23 줄
using System;using System.Linq;class Program{ static void Main() { int n = int.Parse(Console.ReadLine()); int[] b = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); long[] d = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(long.Parse).ToArray(); long carry = long.Parse(Console.ReadLine().Trim()); // 10^12: int로는 넘친다 // C#의 %는 나누어지는 수의 부호를 따른다(-7 % 3 == -1) → b를 더해 다시 나눈다 for (int i = n - 1; i >= 0; i--) { long s = d[i] + carry; d[i] = (s % b[i] + b[i]) % b[i]; carry = (s - d[i]) / b[i]; // s - 칸은 b로 딱 나누어떨어진다: 내림 몫 } Console.WriteLine(string.Join(" ", d)); Console.WriteLine(carry); }}
C++main.cpp · 21 줄
#include <iostream>#include <vector>int main() { int n; std::cin >> n; std::vector<long long> b(n), d(n); for (auto& x : b) std::cin >> x; for (auto& x : d) std::cin >> x; long long carry; // t는 10^12까지: int로는 넘친다 std::cin >> carry; // C++의 %는 0 쪽으로 버린 나눗셈의 나머지라 음수가 나올 수 있다 → b를 더해 다시 나눈다 for (int i = n - 1; i >= 0; i--) { long long s = d[i] + carry; d[i] = (s % b[i] + b[i]) % b[i]; carry = (s - d[i]) / b[i]; // s - 칸은 b로 딱 나누어떨어진다: 내림 몫 } for (int i = 0; i < n; i++) std::cout << (i ? " " : "") << d[i]; std::cout << '\n' << carry << '\n';}
Cmain.c · 20 줄
#include <stdio.h>int main(void) { int n, b[10]; long long d[10], carry; /* t는 10^12까지: int로는 넘친다 */ scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &b[i]); for (int i = 0; i < n; i++) scanf("%lld", &d[i]); scanf("%lld", &carry); /* C의 %는 0 쪽으로 버린 나눗셈의 나머지라 음수가 나올 수 있다 → b를 더해 다시 나눈다 */ for (int i = n - 1; i >= 0; i--) { long long s = d[i] + carry; d[i] = (s % b[i] + b[i]) % b[i]; carry = (s - d[i]) / b[i]; /* s - 칸은 b로 딱 나누어떨어진다: 내림 몫 */ } for (int i = 0; i < n; i++) printf(i ? " %lld" : "%lld", d[i]); printf("\n%lld\n", carry); return 0;}
Craykonmain.cray · 15 줄
n = 콘솔.줄읽기().수로변환();b = 콘솔.수들읽기();d = 콘솔.수들읽기();carry = 콘솔.줄읽기().수로변환(); // 10^12는 2^53 안이라 정확하다// 크레이콘의 %도 나누어지는 수의 부호를 따른다(-7 % 3 == -1) → b를 더해 다시 나눈다// 수학.몫은 0 쪽으로 버리니, 내림 몫은 (s - 칸) / b로 구한다(딱 나누어떨어진다)반복 (i = n - 1; i >= 0; i--){ s = d[i] + carry; d[i] = (s % b[i] + b[i]) % b[i]; carry = (s - d[i]) / b[i];}콘솔.쓰기(d.잇기(" "));콘솔.쓰기(carry);