번호 전광판은 숫자 하나를 막대 7개로 나타낸다.
숫자마다 켜지는 막대 수는 다음과 같다: 0은 6개, 1은 2개, 2는 5개, 3은 5개, 4는 4개, 5는 5개, 6은 6개, 7은 3개, 8은 7개, 9는 6개.
전광판에 정수 x를 띄우면, x를 십진법으로 앞에 0을 붙이지 않고 쓴 숫자들이 켜진다.
0은 숫자 0 하나로 띄운다.
x의 막대 수는 켜진 숫자들의 막대 수를 모두 더한 값이다.
예를 들어 108의 막대 수는 2 + 6 + 7 = 15이고, 7의 막대 수는 3이다.
질문마다 L 이상 R 이하의 정수 가운데 막대 수가 정확히 S인 것이 몇 개인지 출력하라.
그런 정수가 없으면 0을 출력한다.
입력
첫 줄에 질문 수 Q, 다음 Q줄에 질문마다 "L R S"가 빈칸 하나로 나뉘어 주어진다. 1 ≤ Q ≤ 2,000, 0 ≤ L ≤ R ≤ 10^15(1,000,000,000,000,000), 1 ≤ S ≤ 200. 모두 정수다
출력
Q줄: 질문마다 개수 하나(쉼표 없이 숫자만)
예시 1 · stdin
3
1 20 5
0 9 6
100 200 15
stdout
4
3
6
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
R은 10^15까지라 하나씩 세 볼 수 없어요. 자릿수 DP로 풀어요: ways[k][s] = 숫자 k개를 아무렇게나 늘어놓았을 때 막대 수 합이 s인 경우의 수(k = 16, s ≤ 112면 충분해요). 'n 이하에서 막대 수가 S인 수' count(n)을 만들고 답은 count(R) − count(L − 1)이에요. count(n)은 세 부분이에요: ① 0 자신(막대 6개) ② n보다 자릿수가 적은 수 — 첫 숫자는 1~9이고 나머지 k − 1자리는 ways로 ③ n과 자릿수가 같은 수 — 앞에서부터 n과 같은 숫자를 따라가다가 i번째 자리에서 처음 더 작은 숫자 d를 고르면 뒤는 ways[남은 자리][남은 막대]예요(첫 자리는 1부터). 끝까지 따라간 n 자신도 하나 세요. 예시: 1~20에서 막대 5개는 2, 3, 5, 17(2 + 3)이라 4개예요. 함정 하나: 자릿수 합 세기의 흔한 풀이처럼 짧은 수에 앞 0을 붙여 같은 길이로 세면 틀려요 — 자릿수 합에서는 0이 0이라 괜찮았지만 여기서는 앞 0마다 막대 6개가 켜진 셈이 돼요. 자릿수마다 따로 세거나 '아직 숫자를 쓰기 시작했는가'를 상태에 넣어요. 함정 둘: 0 자신을 빠뜨리면 L = 0, S = 6인 질문이 하나 모자라요. 함정 셋: count(R) − count(L)로 빼면 L 자신이 빠져요. 함정 넷: 전광판마다 7을 막대 4개로, 6·9를 5개로 그리기도 해요 — 이 문제의 표(7은 3개, 6·9는 6개)대로 써요. 함정 다섯: 답은 10^15에 가까워서 32비트 int(약 21억)를 넘어요. C·C++ long long, Java·C# long이 필요하고(Java는 int에 +=로 long을 더해도 컴파일되고 조용히 잘려요 — 복합 대입이 저절로 형 변환을 해요. C#은 컴파일 오류가 나요), 입력도 Long.parseLong·long.Parse·%lld로 읽어요. Python 정수는 끝이 없고, JavaScript·TypeScript·크레이콘의 수는 배정밀도 실수라 2^53(약 9×10^15)까지 정확해서 그대로 돼요. 수를 문자열로 바꾸는 법: Python str(n), JS·TS String(n), Java Long.toString(n), C# n.ToString(), C snprintf(buf, size, "%lld", n), C++ std::to_string(n), 크레이콘 "" + n(10^15도 지수 없이 써져요)과 digits[i].수로변환().
Pythonmain.py · 53 줄
import sysSEG = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6] # 숫자 0~9를 띄울 때 켜지는 막대 수MAXLEN = 16 # 10^15는 16자리MAXS = 7 * MAXLEN# ways[k][s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수ways = [[0] * (MAXS + 1) for _ in range(MAXLEN + 1)]ways[0][0] = 1for k in range(1, MAXLEN + 1): for s in range(MAXS + 1): if ways[k - 1][s]: for d in range(10): ways[k][s + SEG[d]] += ways[k - 1][s]def tail(k, s): """뒤에 숫자 k개가 남았고 막대를 s개 더 켜야 할 때의 경우의 수""" return ways[k][s] if 0 <= s <= MAXS else 0def count_upto(n, S): """0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수""" if n < 0: return 0 total = 1 if S == SEG[0] else 0 # 0은 숫자 0 하나로 띄운다 if n == 0: return total digits = str(n) length = len(digits) # n보다 자릿수가 적은 수: 첫 숫자는 1~9(앞에 0을 붙이지 않는다), 나머지는 아무 숫자 for k in range(1, length): for d in range(1, 10): total += tail(k - 1, S - SEG[d]) # n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 rest = S for i, ch in enumerate(digits): c = int(ch) for d in range(1 if i == 0 else 0, c): total += tail(length - 1 - i, rest - SEG[d]) rest -= SEG[c] if rest == 0: total += 1 # n 자신 return totaldata = sys.stdin.read().split()q = int(data[0])out = []for i in range(q): lo, hi, s = int(data[1 + 3 * i]), int(data[2 + 3 * i]), int(data[3 + 3 * i]) out.append(str(count_upto(hi, s) - count_upto(lo - 1, s)))print("\n".join(out))
JavaScriptmain.js · 50 줄
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const SEG = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]; // 숫자 0~9를 띄울 때 켜지는 막대 수const MAXLEN = 16; // 10^15는 16자리const MAXS = 7 * MAXLEN;// ways[k][s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수// 가장 큰 값도 10^15쯤이라 number(2^53까지 정확)로 충분하다const ways = Array.from({ length: MAXLEN + 1 }, () => new Array(MAXS + 1).fill(0));ways[0][0] = 1;for (let k = 1; k <= MAXLEN; k++) { for (let s = 0; s <= MAXS; s++) { if (ways[k - 1][s] === 0) continue; for (let d = 0; d < 10; d++) ways[k][s + SEG[d]] += ways[k - 1][s]; }}const tail = (k, s) => (s >= 0 && s <= MAXS ? ways[k][s] : 0);// 0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수function countUpto(n, S) { if (n < 0) return 0; let total = S === SEG[0] ? 1 : 0; // 0은 숫자 0 하나로 띄운다 if (n === 0) return total; const digits = String(n); const len = digits.length; // n보다 자릿수가 적은 수: 첫 숫자는 1~9, 나머지는 아무 숫자 for (let k = 1; k < len; k++) { for (let d = 1; d <= 9; d++) total += tail(k - 1, S - SEG[d]); } // n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 let rest = S; for (let i = 0; i < len; i++) { const c = digits.charCodeAt(i) - 48; for (let d = i === 0 ? 1 : 0; d < c; d++) total += tail(len - 1 - i, rest - SEG[d]); rest -= SEG[c]; } if (rest === 0) total += 1; // n 자신 return total;}const q = Number(data[0]);const out = [];for (let i = 0; i < q; i++) { const lo = Number(data[1 + 3 * i]); const hi = Number(data[2 + 3 * i]); const s = Number(data[3 + 3 * i]); out.push(countUpto(hi, s) - countUpto(lo - 1, s));}console.log(out.join("\n"));
TypeScriptmain.ts · 54 줄
import { readFileSync } from "node:fs";const data: string[] = readFileSync(0, "utf8").trim().split(/\s+/);const SEG: readonly number[] = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]; // 숫자 0~9를 띄울 때 켜지는 막대 수const MAXLEN = 16; // 10^15는 16자리const MAXS = 7 * MAXLEN;// ways[k][s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수// 가장 큰 값도 10^15쯤이라 number(2^53까지 정확)로 충분하다const ways: number[][] = Array.from({ length: MAXLEN + 1 }, () => new Array<number>(MAXS + 1).fill(0));ways[0][0] = 1;for (let k = 1; k <= MAXLEN; k++) { for (let s = 0; s <= MAXS; s++) { if (ways[k - 1][s] === 0) continue; for (let d = 0; d < 10; d++) ways[k][s + SEG[d]] += ways[k - 1][s]; }}function tail(k: number, s: number): number { return s >= 0 && s <= MAXS ? ways[k][s] : 0;}// 0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수function countUpto(n: number, S: number): number { if (n < 0) return 0; let total = S === SEG[0] ? 1 : 0; // 0은 숫자 0 하나로 띄운다 if (n === 0) return total; const digits = String(n); const len = digits.length; // n보다 자릿수가 적은 수: 첫 숫자는 1~9, 나머지는 아무 숫자 for (let k = 1; k < len; k++) { for (let d = 1; d <= 9; d++) total += tail(k - 1, S - SEG[d]); } // n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 let rest = S; for (let i = 0; i < len; i++) { const c = digits.charCodeAt(i) - 48; for (let d = i === 0 ? 1 : 0; d < c; d++) total += tail(len - 1 - i, rest - SEG[d]); rest -= SEG[c]; } if (rest === 0) total += 1; // n 자신 return total;}const q = Number(data[0]);const out: number[] = [];for (let i = 0; i < q; i++) { const lo = Number(data[1 + 3 * i]); const hi = Number(data[2 + 3 * i]); const s = Number(data[3 + 3 * i]); out.push(countUpto(hi, s) - countUpto(lo - 1, s));}console.log(out.join("\n"));
JavaMain.java · 55 줄
import java.io.*;import java.util.*;public class Main { static final int[] SEG = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; // 숫자 0~9를 띄울 때 켜지는 막대 수 static final int MAXLEN = 16; // 10^15는 16자리 static final int MAXS = 7 * MAXLEN; // ways[k][s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수 static final long[][] ways = new long[MAXLEN + 1][MAXS + 1]; static long tail(int k, int s) { return s >= 0 && s <= MAXS ? ways[k][s] : 0; } // 0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수(답이 10^15까지 가서 long) static long countUpto(long n, int S) { if (n < 0) return 0; long total = S == SEG[0] ? 1 : 0; // 0은 숫자 0 하나로 띄운다 if (n == 0) return total; String digits = Long.toString(n); int len = digits.length(); // n보다 자릿수가 적은 수: 첫 숫자는 1~9, 나머지는 아무 숫자 for (int k = 1; k < len; k++) for (int d = 1; d <= 9; d++) total += tail(k - 1, S - SEG[d]); // n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 int rest = S; for (int i = 0; i < len; i++) { int c = digits.charAt(i) - '0'; for (int d = i == 0 ? 1 : 0; d < c; d++) total += tail(len - 1 - i, rest - SEG[d]); rest -= SEG[c]; } if (rest == 0) total++; // n 자신 return total; } public static void main(String[] args) throws IOException { ways[0][0] = 1; for (int k = 1; k <= MAXLEN; k++) for (int s = 0; s <= MAXS; s++) if (ways[k - 1][s] != 0) for (int d = 0; d < 10; d++) ways[k][s + SEG[d]] += ways[k - 1][s]; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int q = Integer.parseInt(br.readLine().trim()); StringBuilder sb = new StringBuilder(); for (int i = 0; i < q; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); long lo = Long.parseLong(st.nextToken()); long hi = Long.parseLong(st.nextToken()); int s = Integer.parseInt(st.nextToken()); sb.append(countUpto(hi, s) - countUpto(lo - 1, s)).append('\n'); } System.out.print(sb); }}
C#Main.cs · 57 줄
using System;using System.Text;class Program{ static readonly int[] Seg = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 }; // 숫자 0~9를 띄울 때 켜지는 막대 수 const int MaxLen = 16; // 10^15는 16자리 const int MaxS = 7 * MaxLen; // ways[k, s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수 static readonly long[,] Ways = new long[MaxLen + 1, MaxS + 1]; static long Tail(int k, int s) => s >= 0 && s <= MaxS ? Ways[k, s] : 0; // 0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수(답이 10^15까지 가서 long) static long CountUpto(long n, int S) { if (n < 0) return 0; long total = S == Seg[0] ? 1 : 0; // 0은 숫자 0 하나로 띄운다 if (n == 0) return total; string digits = n.ToString(); int len = digits.Length; // n보다 자릿수가 적은 수: 첫 숫자는 1~9, 나머지는 아무 숫자 for (int k = 1; k < len; k++) for (int d = 1; d <= 9; d++) total += Tail(k - 1, S - Seg[d]); // n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 int rest = S; for (int i = 0; i < len; i++) { int c = digits[i] - '0'; for (int d = i == 0 ? 1 : 0; d < c; d++) total += Tail(len - 1 - i, rest - Seg[d]); rest -= Seg[c]; } if (rest == 0) total++; // n 자신 return total; } static void Main() { Ways[0, 0] = 1; for (int k = 1; k <= MaxLen; k++) for (int s = 0; s <= MaxS; s++) if (Ways[k - 1, s] != 0) for (int d = 0; d < 10; d++) Ways[k, s + Seg[d]] += Ways[k - 1, s]; int q = int.Parse(Console.ReadLine()!.Trim()); var sb = new StringBuilder(); for (int i = 0; i < q; i++) { var p = Console.ReadLine()!.Split(' ', StringSplitOptions.RemoveEmptyEntries); long lo = long.Parse(p[0]); long hi = long.Parse(p[1]); int s = int.Parse(p[2]); sb.Append(CountUpto(hi, s) - CountUpto(lo - 1, s)).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 52 줄
#include <array>#include <iostream>#include <string>constexpr int MAXLEN = 16; // 10^15는 16자리constexpr int MAXS = 7 * MAXLEN;constexpr std::array<int, 10> SEG = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; // 숫자 0~9를 띄울 때 켜지는 막대 수// ways[k][s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수std::array<std::array<long long, MAXS + 1>, MAXLEN + 1> ways{};long long tail(int k, int s) { return s >= 0 && s <= MAXS ? ways[k][s] : 0; }// 0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수(답이 10^15까지 가서 long long)long long countUpto(long long n, int S) { if (n < 0) return 0; long long total = S == SEG[0] ? 1 : 0; // 0은 숫자 0 하나로 띄운다 if (n == 0) return total; const std::string digits = std::to_string(n); const int len = static_cast<int>(digits.size()); // n보다 자릿수가 적은 수: 첫 숫자는 1~9, 나머지는 아무 숫자 for (int k = 1; k < len; k++) for (int d = 1; d <= 9; d++) total += tail(k - 1, S - SEG[d]); // n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 int rest = S; for (int i = 0; i < len; i++) { int c = digits[i] - '0'; for (int d = i == 0 ? 1 : 0; d < c; d++) total += tail(len - 1 - i, rest - SEG[d]); rest -= SEG[c]; } if (rest == 0) total++; // n 자신 return total;}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); ways[0][0] = 1; for (int k = 1; k <= MAXLEN; k++) for (int s = 0; s <= MAXS; s++) if (ways[k - 1][s]) for (int d = 0; d < 10; d++) ways[k][s + SEG[d]] += ways[k - 1][s]; int q; std::cin >> q; for (int i = 0; i < q; i++) { long long lo, hi; int s; std::cin >> lo >> hi >> s; std::cout << countUpto(hi, s) - countUpto(lo - 1, s) << '\n'; }}
Cmain.c · 49 줄
#include <stdio.h>#define MAXLEN 16 /* 10^15는 16자리 */#define MAXS (7 * MAXLEN)static const int SEG[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; /* 숫자 0~9를 띄울 때 켜지는 막대 수 *//* ways[k][s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수 */static long long ways[MAXLEN + 1][MAXS + 1];static long long tail(int k, int s) { return s >= 0 && s <= MAXS ? ways[k][s] : 0; }/* 0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수(답이 10^15까지 가서 long long) */static long long count_upto(long long n, int S) { if (n < 0) return 0; long long total = S == SEG[0] ? 1 : 0; /* 0은 숫자 0 하나로 띄운다 */ if (n == 0) return total; char digits[24]; int len = snprintf(digits, sizeof digits, "%lld", n); /* n보다 자릿수가 적은 수: 첫 숫자는 1~9, 나머지는 아무 숫자 */ for (int k = 1; k < len; k++) for (int d = 1; d <= 9; d++) total += tail(k - 1, S - SEG[d]); /* n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 */ int rest = S; for (int i = 0; i < len; i++) { int c = digits[i] - '0'; for (int d = i == 0 ? 1 : 0; d < c; d++) total += tail(len - 1 - i, rest - SEG[d]); rest -= SEG[c]; } if (rest == 0) total++; /* n 자신 */ return total;}int main(void) { ways[0][0] = 1; for (int k = 1; k <= MAXLEN; k++) for (int s = 0; s <= MAXS; s++) if (ways[k - 1][s]) for (int d = 0; d < 10; d++) ways[k][s + SEG[d]] += ways[k - 1][s]; int q; if (scanf("%d", &q) != 1) return 0; for (int i = 0; i < q; i++) { long long lo, hi; int s; scanf("%lld %lld %d", &lo, &hi, &s); printf("%lld\n", count_upto(hi, s) - count_upto(lo - 1, s)); } return 0;}
Craykonmain.cray · 90 줄
SEG = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]; // 숫자 0~9를 띄울 때 켜지는 막대 수MAXLEN = 16; // 10^15는 16자리MAXS = 7 * MAXLEN;// ways[k][s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수ways = [];반복 (k = 0; k <= MAXLEN; k++){ ways.넣기(새목록(MAXS + 1, 0));}ways[0][0] = 1;반복 (k = 1; k <= MAXLEN; k++){ 반복 (s = 0; s <= MAXS; s++) { 만약 (ways[k - 1][s] != 0) { 반복 (d = 0; d < 10; d++) { ways[k][s + SEG[d]] += ways[k - 1][s]; } } }}// 뒤에 숫자 k개가 남았고 막대를 s개 더 켜야 할 때의 경우의 수뒤(k, s){ 만약 (s < 0 || s > MAXS) { 돌려주기 0; } 돌려주기 ways[k][s];}// 0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수세기(n, S){ 만약 (n < 0) { 돌려주기 0; } total = 0; 만약 (S == SEG[0]) { total = 1; } 만약 (n == 0) { 돌려주기 total; } digits = "" + n; len = digits.길이; // n보다 자릿수가 적은 수: 첫 숫자는 1~9, 나머지는 아무 숫자 반복 (k = 1; k < len; k++) { 반복 (d = 1; d <= 9; d++) { total += 뒤(k - 1, S - SEG[d]); } } // n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 rest = S; 반복 (i = 0; i < len; i++) { c = digits[i].수로변환(); 시작 = 0; 만약 (i == 0) { 시작 = 1; } 반복 (d = 시작; d < c; d++) { total += 뒤(len - 1 - i, rest - SEG[d]); } rest -= SEG[c]; } 만약 (rest == 0) { total += 1; } 돌려주기 total;}q = 콘솔.줄읽기().공백제거().수로변환();반복 (i = 0; i < q; i++){ p = 콘솔.수들읽기(); 콘솔.쓰기(세기(p[1], p[2]) - 세기(p[0] - 1, p[2]));}