호반우가 학교에 지각한 이유 2
문제
이세계를 모험할 때는 무기가 필요한 법이기에 호반우는 현재 신에게 받은 소수소수검의 사용법을 익히고 있다.
소수소수검을 사용하기 위해서는 검이 제시하는 두 자릿수의 소수 A,B와 양의 정수 N을 이용해 소수소수를 만들어야 한다.
소수소수란 해당 수 자체가 소수일 필요는 없지만 모든 연속된 두 자릿수가 소수인 수를 말한다.
예를 들어 973은 97과 73이 소수이므로 소수소수가 되지만, 937은 93이 소수가 아니기에 소수소수가 아니다.
이때 소수소수를 만들 때 한가지 제한사항이 있는데 처음 두 자릿수는 A이고 마지막 두 자릿수는 B인 N 자릿수의 소수소수를 만들어야 한다.
아직 검의 사용법에 익숙하지 않은 호반우를 도와 소수소수를 만들어 주자.
입력
첫 번째 줄에 소수 A,B와 양의 정수 N이 공백을 두고 주어진다. (7 <= N <= 100, 11 <= A,B <= 97)
출력
주어진 수들로 소수소수를 만들 수 있다면 소수소수를 아무거나 하나 출력하고 만들 수 없다면 -1을 출력한다.
1
2
3
4
5
예제 입력 1
47 37 7
예제 출력 1
4719737
4719737은 모든 연속된 두 자릿수 47,71,19,97,73,37이 소수이므로 소수소수이다.
1
2
3
4
5
예제 입력 2
17 23 10
예제 출력 2
-1
풀이
뭔가 codeforce 느낌이 섞인 애드 훅 문제라고 생각이 든다.
풀면서 나름 재미있었다.
접근 방법으로 일단 있는 소수들을 다 적어본다.
그러면 두자리 소수들은 모두 1, 3, 7, 9로 끝난다는 것을 알 수 있다.
그렇기에 두번째로 받는 m의 십의 자리 수는 1, 3, 7, 9여야 한다.
이제 중간을 이어줄 소수를 찾아야 하는데 11을 사용하면 전부 다 된다.
길이인 N이 7이기 때문에 n의 끝자리와 m의 첫자리를 소수들로 잇는 것이 가능하다.
11이 소수이고, 13, 17, 19가 모두 소수이기에 끝을 이을 수 있고, 31, 71도 소수이다.
91은 소수가 아니기에 n의 끝자리가 9일 때만 97, 71, 11.. 이렇게 이어주면 해결이 된다.
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
using namespace std;
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
long long ans;
long long cnt = 0;
int n, m, t;
cin >> n >> m >> t;
if(m/10==1 || m/10==3 || m/10==7 || m/10==9){
cout << n;
if(n%10==9){
cout <<"7";
t--;
}
for(int i=0;i<t-4;i++){
cout << "1";
}
cout << m;
}
else cout << "-1";
return 0;
// A는 무조건 1,3,7,9로 끝남., N은 7보다 크다는 조건도 있네..
// 0,2,4,5,6,8로 끝나면 다 불가능
// 1로 시작하면 1,3,7,9 무조건 가능
// 3으로 시작하면 31, 11~가능
// 7로 시작하면 71, 11, 11 ~가능
// 9로 시작하면 97 71 가능~
}