문제
https://www.acmicpc.net/problem/14382
문제해설
숫자 N이 주어진다.
N에 1, 2, 3, … 을 곱해가면서
구성되어있는 수 들을 모두 체크한다.
0부터 9까지의 모든 수가 체크되는 순간 해당 수를 출력하면 된다.
문제풀이
이 문제는 내가 알고리즘을 처음 시작할 때 접했다면
별 생각없이 그냥 풀어냈을 수도 있다.
그냥 구현하면 되는 것처럼 느껴지지만 증명이 안되서 확신이 없었다.
생각을 해보니 불가능한 경우는 0밖에 존재하지 않았다.
그리고 최악의 경우로 가장 많이 돌아야 하는 수는 2였다.
2는 총 45번이 돌아야 답이 나온다.
나머지 수들은 전부 그것보다는 적게 돌아도 되었다.
결국 문제 그대로 구현만 해주면 된다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n; cin >> n;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
if (x == 0) {
cout << "Case #" << i << ": INSOMNIA\n";
continue;
}
bool arr[10] = { false };
for (int j = 1;; j++) {
int tmp = x * j;
string s = to_string(tmp);
for (int k = 0; k < s.length(); k++) {
arr[s[k] - '0'] = true;
}
bool flag = false;
for (int k = 0; k < 10; k++) {
if (arr[k] == false) {
flag = true;
break;
}
}
if (!flag) {
cout << "Case #" << i << ": " << tmp << "\n";
break;
}
}
}
return 0;
}