현관 자물쇠의 비밀번호는 숫자 L자리이고, 0으로 시작할 수도 있다.
자판을 살펴보니 숫자 키 가운데 k개가 닳아 있다.
비밀번호는 닳은 키의 숫자만으로 이루어지고, 닳은 키의 숫자는 저마다 한 번 이상 쓰인다.
이 자물쇠는 같은 숫자를 잇달아 누르지 못하게 되어 있어서, 비밀번호에서 이웃한 두 자리의 숫자는 서로 다르다.
주인은 비밀번호의 자리 숫자를 모두 더하면 S가 된다는 것만 기억한다.
이 조건을 모두 지키는 비밀번호가 몇 개인지 첫 줄에 출력하라.
하나 이상 있으면, 그 가운데 수로 보아 가장 작은 것을 둘째 줄에, 가장 큰 것을 셋째 줄에 출력한다.
비밀번호는 앞의 0을 빼지 않고 L자리를 그대로 쓴다.
조건에 맞는 비밀번호가 하나뿐이면 둘째 줄과 셋째 줄에 같은 것을 쓴다.
하나도 없으면 첫 줄에 0만 출력한다.
입력
첫 줄에 L, k, S가 빈칸 하나씩 띄워 주어진다. 둘째 줄에 닳은 키의 숫자 k개가 빈칸 하나씩 띄워 주어진다. 닳은 키의 숫자는 0 이상 9 이하이고 서로 다르며, 차례는 정해져 있지 않다. 1 ≤ L ≤ 5, 1 ≤ k ≤ 10, 0 ≤ S ≤ 45
출력
첫 줄에 조건에 맞는 비밀번호의 수. 하나 이상이면 둘째 줄에 가장 작은 비밀번호, 셋째 줄에 가장 큰 비밀번호(모두 L자리)
예시 1 · stdin
4 2 14
0 7
stdout
2
0707
7070
예시 2 · stdin
3 2 3
1 2
stdout
0
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
조건을 식 하나로 풀기 어려울 때는 후보를 모두 만들어 하나씩 검사하면 돼요. 여기서는 00…0부터 99…9까지 10^L개이고, L이 5 이하라 많아야 10만 개예요. 함정 하나: 비밀번호는 수가 아니라 숫자 L개를 늘어놓은 것이에요. 반복을 10^(L−1)부터 시작하면 첫 예시의 0707처럼 0으로 시작하는 답을 통째로 놓쳐요. 함정 둘: 자릿수를 while (x > 0)으로 꺼내면 앞자리의 0은 보지 않고 끝나요. 둘째 예시에서 12(= 012)의 1과 2만 보고 닳은 키 1, 2에 맞는다고 세어 버리니, 꼭 L번 꺼내요. 함정 셋: '닳은 키만 쓴다'와 '닳은 키를 모두 쓴다'는 서로 다른 조건이라 둘 다 검사해야 해요. 닳은 키가 1, 2, 3인데 121을 답으로 세면 틀려요. Python은 글자 집합을 견주는 set(pin) != worn 한 번으로 두 조건을 함께 봐요. 함정 넷: 찾은 답을 수로 들고 있다가 그대로 출력하면 0707이 707로 나와요. 앞을 0으로 채우는 방법은 언어마다 달라요: Python f"{code:0{length}d}", JavaScript·TypeScript String(code).padStart(length, "0"), Java String.format("%0" + length + "d", code), C# code.ToString("D" + length), C printf("%0*d", length, code)(너비를 * 자리의 인수로 줘요), C++ std::setfill('0') << std::setw(length)(setw는 바로 다음 값 하나에만 들어서 값마다 다시 써요), 크레이콘 ("" + code).앞채우기(length, "0").
Pythonmain.py · 22 줄
length, k, target = map(int, input().split())worn = set(input().split()) # 닳은 키를 글자 집합으로: {"0", "7"}count = 0first = last = ""for code in range(10 ** length): # 0부터: 0으로 시작하는 비밀번호도 있다 pin = f"{code:0{length}d}" # 앞을 0으로 채워 length자리로 if set(pin) != worn: # 닳은 키만, 그리고 빠짐없이 continue if any(a == b for a, b in zip(pin, pin[1:])): # 이웃한 자리가 같으면 안 된다 continue if sum(map(int, pin)) != target: continue count += 1 if count == 1: first = pin last = pin # 작은 수부터 보므로 마지막에 본 것이 가장 크다print(count)if count > 0: print(first) print(last)
JavaScriptmain.js · 33 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [length, , target] = lines[0].trim().split(/\s+/).map(Number);const worn = lines[1].trim().split(/\s+/).map(Number);// 비밀번호 한 개가 세 조건을 모두 지키는지 본다function fits(pin) { const used = new Set(pin); // 문자열을 넣으면 글자 하나하나가 들어간다 if (used.size !== worn.length || !worn.every((d) => used.has(String(d)))) return false; let sum = 0; for (let i = 0; i < pin.length; i++) { if (i > 0 && pin[i] === pin[i - 1]) return false; // 이웃한 자리가 같으면 안 된다 sum += Number(pin[i]); } return sum === target;}let count = 0;let first = "";let last = "";// 0부터: 0으로 시작하는 비밀번호도 있다for (let code = 0; code < 10 ** length; code++) { const pin = String(code).padStart(length, "0"); // 앞을 0으로 채워 length자리로 if (!fits(pin)) continue; count++; if (count === 1) first = pin; last = pin; // 작은 수부터 보므로 마지막에 본 것이 가장 크다}console.log(count);if (count > 0) { console.log(first); console.log(last);}
TypeScriptmain.ts · 35 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [length, , target] = lines[0].trim().split(/\s+/).map(Number);const worn: number[] = lines[1].trim().split(/\s+/).map(Number);// 비밀번호 한 개가 세 조건을 모두 지키는지 본다function fits(pin: string): boolean { const used = new Set<string>(pin); // 문자열을 넣으면 글자 하나하나가 들어간다 if (used.size !== worn.length || !worn.every((d) => used.has(String(d)))) return false; let sum = 0; for (let i = 0; i < pin.length; i++) { if (i > 0 && pin[i] === pin[i - 1]) return false; // 이웃한 자리가 같으면 안 된다 sum += Number(pin[i]); } return sum === target;}let count = 0;let first = "";let last = "";// 0부터: 0으로 시작하는 비밀번호도 있다for (let code = 0; code < 10 ** length; code++) { const pin: string = String(code).padStart(length, "0"); // 앞을 0으로 채워 length자리로 if (!fits(pin)) continue; count++; if (count === 1) first = pin; last = pin; // 작은 수부터 보므로 마지막에 본 것이 가장 크다}console.log(count);if (count > 0) { console.log(first); console.log(last);}
JavaMain.java · 49 줄
import java.util.*;public class Main { static int length, target; static boolean[] worn = new boolean[10]; // 비밀번호 한 개가 세 조건을 모두 지키는지 본다 static boolean fits(int code) { boolean[] used = new boolean[10]; int sum = 0, prev = -1, x = code; // while (x > 0)이 아니라 꼭 length번: 앞자리의 0도 자리다 for (int i = 0; i < length; i++) { int d = x % 10; x /= 10; if (!worn[d] || d == prev) return false; // 닳지 않은 키이거나 이웃과 같다 used[d] = true; sum += d; prev = d; } for (int d = 0; d < 10; d++) if (worn[d] && !used[d]) return false; // 닳았는데 쓰지 않은 키 return sum == target; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); length = sc.nextInt(); int k = sc.nextInt(); target = sc.nextInt(); for (int i = 0; i < k; i++) worn[sc.nextInt()] = true; int limit = 1; for (int i = 0; i < length; i++) limit *= 10; int count = 0, first = -1, last = -1; for (int code = 0; code < limit; code++) { // 0부터: 0으로 시작하는 비밀번호도 있다 if (!fits(code)) continue; count++; if (first < 0) first = code; last = code; } System.out.println(count); if (count > 0) { String format = "%0" + length + "d"; // 앞을 0으로 채워 length자리로 System.out.println(String.format(format, first)); System.out.println(String.format(format, last)); } }}
C#Main.cs · 56 줄
using System;using System.Linq;class Program{ static int length, target; static bool[] worn = new bool[10]; // 비밀번호 한 개가 세 조건을 모두 지키는지 본다 static bool Fits(int code) { var used = new bool[10]; int sum = 0, prev = -1, x = code; // while (x > 0)이 아니라 꼭 length번: 앞자리의 0도 자리다 for (int i = 0; i < length; i++) { int d = x % 10; x /= 10; if (!worn[d] || d == prev) return false; // 닳지 않은 키이거나 이웃과 같다 used[d] = true; sum += d; prev = d; } for (int d = 0; d < 10; d++) if (worn[d] && !used[d]) return false; // 닳았는데 쓰지 않은 키 return sum == target; } static void Main() { int[] head = Console.ReadLine()!.Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); length = head[0]; target = head[2]; foreach (string s in Console.ReadLine()!.Split(' ', StringSplitOptions.RemoveEmptyEntries)) worn[int.Parse(s)] = true; int limit = 1; for (int i = 0; i < length; i++) limit *= 10; int count = 0, first = -1, last = -1; for (int code = 0; code < limit; code++) // 0부터: 0으로 시작하는 비밀번호도 있다 { if (!Fits(code)) continue; count++; if (first < 0) first = code; last = code; } Console.WriteLine(count); if (count > 0) { string format = "D" + length; // "D4"는 앞을 0으로 채운 4자리 Console.WriteLine(first.ToString(format)); Console.WriteLine(last.ToString(format)); } }}
C++main.cpp · 49 줄
#include <array>#include <iomanip>#include <iostream>int length, target;std::array<bool, 10> worn{};// 비밀번호 한 개가 세 조건을 모두 지키는지 본다bool fits(int code) { std::array<bool, 10> used{}; int sum = 0, prev = -1, x = code; // while (x > 0)이 아니라 꼭 length번: 앞자리의 0도 자리다 for (int i = 0; i < length; i++) { int d = x % 10; x /= 10; if (!worn[d] || d == prev) return false; // 닳지 않은 키이거나 이웃과 같다 used[d] = true; sum += d; prev = d; } return used == worn && sum == target; // 닳은 키를 빠짐없이 썼는지는 배열끼리 견준다}int main() { int k; std::cin >> length >> k >> target; for (int i = 0; i < k; i++) { int d; std::cin >> d; worn[d] = true; } int limit = 1; for (int i = 0; i < length; i++) limit *= 10; int count = 0, first = -1, last = -1; for (int code = 0; code < limit; code++) { // 0부터: 0으로 시작하는 비밀번호도 있다 if (!fits(code)) continue; count++; if (first < 0) first = code; last = code; } std::cout << count << '\n'; if (count > 0) { // setfill은 한 번 정하면 계속 가지만 setw는 바로 다음 값 하나에만 듣는다 std::cout << std::setfill('0') << std::setw(length) << first << '\n' << std::setw(length) << last << '\n'; }}
Cmain.c · 51 줄
#include <stdbool.h>#include <stdio.h>static int length, target;static bool worn[10];/* 비밀번호 한 개가 세 조건을 모두 지키는지 본다 */static bool fits(int code) { bool used[10] = {false}; int sum = 0, prev = -1, x = code; /* while (x > 0)이 아니라 꼭 length번: 앞자리의 0도 자리다 */ for (int i = 0; i < length; i++) { int d = x % 10; x /= 10; if (!worn[d] || d == prev) return false; /* 닳지 않은 키이거나 이웃과 같다 */ used[d] = true; sum += d; prev = d; } for (int d = 0; d < 10; d++) if (worn[d] && !used[d]) return false; /* 닳았는데 쓰지 않은 키 */ return sum == target;}int main(void) { int k; if (scanf("%d %d %d", &length, &k, &target) != 3) return 0; for (int i = 0; i < k; i++) { int d; if (scanf("%d", &d) != 1) return 0; worn[d] = true; } int limit = 1; for (int i = 0; i < length; i++) limit *= 10; int count = 0, first = -1, last = -1; for (int code = 0; code < limit; code++) { /* 0부터: 0으로 시작하는 비밀번호도 있다 */ if (!fits(code)) continue; count++; if (first < 0) first = code; last = code; } printf("%d\n", count); if (count > 0) { /* %0*d: 너비를 인수로 받아 앞을 0으로 채운다 */ printf("%0*d\n", length, first); printf("%0*d\n", length, last); } return 0;}
Craykonmain.cray · 68 줄
// 비밀번호 한 개가 세 조건을 모두 지키는지 본다맞나(code, length, target, worn){ used = 새목록(10, 거짓); sum = 0; prev = -1; x = code; // 동안 (x > 0)이 아니라 꼭 length번: 앞자리의 0도 자리다 반복 (i = 0; i < length; i++) { d = x % 10; x = 수학.몫(x, 10); 만약 (!worn[d] || d == prev) { 돌려주기 거짓; // 닳지 않은 키이거나 이웃과 같다 } used[d] = 참; sum += d; prev = d; } 반복 (d = 0; d < 10; d++) { 만약 (worn[d] && !used[d]) { 돌려주기 거짓; // 닳았는데 쓰지 않은 키 } } 돌려주기 sum == target;}head = 콘솔.수들읽기();length = head[0];target = head[2];worn = 새목록(10, 거짓);각각 (d 에서 콘솔.수들읽기()){ worn[d] = 참;}limit = 1;반복 (i = 0; i < length; i++){ limit *= 10;}count = 0;first = -1;last = -1;// 0부터: 0으로 시작하는 비밀번호도 있다반복 (code = 0; code < limit; code++){ 만약 (맞나(code, length, target, worn)) { count += 1; 만약 (first < 0) { first = code; } last = code; }}콘솔.쓰기(count);만약 (count > 0){ // 수를 문자열로 바꾼 다음 앞을 0으로 채워 length자리로 콘솔.쓰기(("" + first).앞채우기(length, "0")); 콘솔.쓰기(("" + last).앞채우기(length, "0"));}